AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (974.7 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

School 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
Center for Combinatorics and LPMC, Nankai University, Tianjin 300000, China
Faculty 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 hierarchyapproximation algorithmMax CutMax Bisection

References

【1】
【1】
 
 
Crossref Google Scholar
Tsinghua Science and Technology
Volume 30 Issue 4,
August 2025
Pages 1885-1896
DOI: 10.26599/TST.2024.9010214

{{item.num}}

Comments on this article

Go to comment

< Back to all reports

Review Status: {{reviewData.commendedNum}} Commended , {{reviewData.revisionRequiredNum}} Revision Required , {{reviewData.notCommendedNum}} Not Commended Under Peer Review

Review Comment

Cite this Report
Close
Close
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

1231

Views

75

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD
Received: 25 June 2024
Revised: 06 September 2024
Accepted: 04 November 2024
Published: 03 March 2025
© The Author(s) 2025.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).