@article{Li2025, 
author = {Guangfeng Li and Jian Sun and Donglei Du and Xiaoyan Zhang},
title = {A Lasserre SDP Rounding Approximation Algorithm for Max Directed 3-Section},
year = {2025},
journal = {Tsinghua Science and Technology},
volume = {30},
number = {4},
pages = {1885-1896},
keywords = {approximation algorithm, Semi-Definite Programming (SDP), Lasserre hierarchy, Max Cut, Max Bisection},
url = {https://www.sciopen.com/article/10.26599/TST.2024.9010214},
doi = {10.26599/TST.2024.9010214},
abstract = {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.}
}