PDF (974.7 KB)

Cite

Collect

Open Access

A Lasserre SDP Rounding Approximation Algorithm for Max Directed 3-Section

Guangfeng Li^¹, Jian Sun^², Donglei Du^³, Xiaoyan Zhang^¹()

1School of Mathematical Science & Institute of Mathematics and Key Laboratory of Ministry of Education Numerical Simulation of Large Scale Complex Systems, Nanjing Normal University, Nanjing 210023, China

2Center for Combinatorics and LPMC, Nankai University, Tianjin 300000, China

3Faculty of Management, University of New Brunswick, Frederiction, E3B5A3, Canada

Show Author Information

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.

Keywords

Semi-Definite Programming (SDP)Lasserre hierarchy approximation algorithm Max Cut Max Bisection

References

[1]

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, vol. 42, no. 6, pp. 1115–1145, 1995.

Crossref Google Scholar

[2]

P. M. B. Vitányi, How well can a graph be n-colored, Discrete Math., vol. 34, no. 1, pp. 69–80, 1981.

Crossref Google Scholar

[3]

D. J. Haglin and S. M. Venkatesan, Approximation and intractability results for the maximum cut problem and its variants, IEEE Trans. Comput., vol. 40, no. 1, pp. 110–113, 1991.

Crossref Google Scholar

[4]

T. Hofmeister and H. Lefmann, A combinatorial design approach to MAXCUT, Random Struct. Alg., vol. 9, nos. 1&2, pp. 163–175, 1996.

Crossref Google Scholar

[5]

G. Andersson, An approximation algorithm for max p-section, in Proc. Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, 1999. pp. 237–247.

[6]

P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies, in Proc. Twenty-Third Annual ACM-SIAM Symp. on Discrete Algorithms, Philadelphia, PA USA, 2012, pp. 373–387.

[7]

P. Austrin, S. Benabbas, and K. Georgiou, Better balance by being biased: A 0.8776-approximation for max bisection, ACM Trans. Algorithms, vol. 13, no. 1, pp. 1–27, 2016.

Google Scholar

[8]

B. Xu, X. Yu, X. Zhang, and Z.-B. Zhang, An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance, Sci. China Math., vol. 57, no. 12, pp. 2437–2462, 2014.

Crossref Google Scholar

[9]

J. Sun, Z.-B. Zhang, Y. Chen, D. Han, D. Du, and X. Zhang, A maximum hypergraph 3-cut problem with limited unbalance: Approximation and analysis, J. Glob. Optim., vol. 87, no. 2, pp. 917–937, 2023.

Google Scholar

[10]

S. Ji, D. Xu, D. Du, L. Gai, and Z. Zhao, Approximation algorithm for the balanced 2-correlation clustering problem, Tsinghua Science and Technology, vol. 27, no. 5, pp. 777–784, 2022.

Crossref Google Scholar

[11]

A. Frieze and M. Jerrum, Improved approximation algorithms for MAX k-CUT and MAX BISECTION, Algorithmica, vol. 18, no. 1, pp. 67–81, 1997.

Crossref Google Scholar

[12]

Y. Ye, A.699-approximation algorithm for max-bisection, Math. Program., vol. 90, no. 1, pp. 101–111, 2001.

[13]

E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random Struct. Algoritms., vol. 20, no. 3, pp. 382–402, 2002.

Crossref Google Scholar

[14]

U. Feige and M. Langberg, The RPR2 rounding technique for semidefinite programs, J. Algoritms., vol. 60, no. 1, pp. 1–23, 2006.

Google Scholar

[15]

U. Feige, M. Karpinski, and M. Langberg, A note on approximating Max-Bisection on regular graphs, Inf. Process. Lett., vol. 79, no. 4, pp. 181–188, 2001.

Crossref Google Scholar

[16]

U. Feige, M. Karpinski, and M. Langberg, Improved approximation of Max-Cut on graphs of bounded degree, J. Algoritms., vol. 43, no. 2, pp. 201–219, 2002.

Google Scholar

[17]

C. Wu, D. Du, and D. Xu, An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems, J. Comb. Optim., vol. 29, no. 1, pp. 53–66, 2015.

Crossref Google Scholar

[18]

D. Katzelnick, A. Pillai, R. Schwartz and M. Singh, An improved approximation algorithm for the Max-3-Section problem, in Proc. 31st annual European Symposium on Algorithms, Amsterdam, The Netherlands, https://doi.org/10.4230/LIPIcs.ESA.2023.69, 2023.

[19]

U. Zwick, Computer assisted proof of optimal approximability results, in Proc. of the 13^th annual ACM-SIAM symposium on Discrete Algorithms, San Francisco, CA, USA, pp. 496–505, 2002.

[20]

K. Zhao and L. Ning, Hybrid navigation method for multiple robots facing dynamic obstacles, Tsinghua Science and Technology, vol. 27, no. 6, pp. 894–901, 2022.

Crossref Google Scholar

[21]

G. Galbiati and F. Maffioli, Approximation algorithms for maximum cut with limited unbalance, Theor. Comput. Sci., vol. 385, nos. 1&3, pp. 78–87, 2007.

Crossref Google Scholar

[22]

U. Feige and M. Goemans, Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT, in Proc. Third Israel Symp. on the Theory of Computing and Systems, Tel Aviv, Israel, 1995, pp. 182–189.

[23]

Q. Han, Y. Ye, and J. Zhang, An improved rounding method and semidefinite programming relaxation for graph partition, Math. Program., vol. 92, no. 3, pp. 509–535, 2002.

Crossref Google Scholar

[24]

Z. Drezner and G. O. Wesolowsky, On the computation of the bivariate normal integral, J. Stat. Comput. Simul., vol. 35, nos. 1&2, pp. 101–107, 1990.

Crossref Google Scholar

[25]

M. Tulsiani, CSP gaps and reductions in the lasserre hierarchy, in Proc. forty-first annual ACM Symp. on Theory of computing, Bethesda, MD, USA, 2009, pp. 303–312

Tsinghua Science and Technology

Volume 30 Issue 4,
August 2025

Pages 1885-1896

DOI: 10.26599/TST.2024.9010214

Cite this article:

Li G, Sun J, Du D, et al. A Lasserre SDP Rounding Approximation Algorithm for Max Directed 3-Section. Tsinghua Science and Technology, 2025, 30(4): 1885-1896. https://doi.org/10.26599/TST.2024.9010214