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.
Publications
- Article type
- Year
- Co-author
Year
Open Access
Issue
Tsinghua Science and Technology 2025, 30(4): 1885-1896
Published: 03 March 2025
Downloads:75
Total 1
京公网安备11010802044758号