.png){kind=icon}
.png){kind=icon}
Return
A Lasserre SDP Rounding Approximation Algorithm for Max Directed 3-Section
.png){kind=icon}
PRE
AI
DOI：10.26599/TST.2024.9010214.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider the Max Directed 3-Section problem, which is closely connected to other well-known graph partition problems, such as Max Cut and Max Bisection. Given an arc-weighted directed graph, the goal of the Max Directed 3-Section problem is to partition the vertex set into three disjoint subsets with equal size, while maximizing the total weight of arcs crossing different vertex subsets. By combining the Lasserre hierarchy with the random hyperplane rounding strategy, we propose a polynomial-time algorithm with approximation ratio of 0.489.
Keywords:
Directed graphs
Programming
Approximation algorithms
Partitioning algorithms
MATLAB
Semi-Definite Programming (SDP)
Lasserre hierarchy
approximation algorithm
Max Cut
Max Bisection
Journal
T
IF:
3.5
Papers:
987
Citations:
2.5K
View more organizations