Sort:
Open Access Issue
A Lasserre SDP Rounding Approximation Algorithm for Max Directed 3-Section
Tsinghua Science and Technology 2025, 30(4): 1885-1896
Published: 03 March 2025
Abstract PDF (974.7 KB) Collect
Downloads:75

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.

Total 1