TY - JOUR
T1 - A maximum hypergraph 3-cut problem with limited unbalance
T2 - approximation and analysis
AU - Sun, Jian
AU - Zhang, Zan Bo
AU - Chen, Yannan
AU - Han, Deren
AU - Du, Donglei
AU - Zhang, Xiaoyan
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2023/11
Y1 - 2023/11
N2 - We consider the max hypergraph 3-cut problem with limited unbalance (MH3C-LU). The objective is to divide the vertex set of an edge-weighted hypergraph H= (V, E, w) into three disjoint subsets V1, V2, and V3 such that the sum of edge weights cross different parts is maximized subject to | | Vi| - | Vl| | ≤ B (∀ i≠ l∈ { 1 , 2 , 3 }) for a given parameter B. This problem is NP-hard because it includes some well-known problems like the max 3-section problem and the max 3-cut problem as special cases. We formulate the MH3C-LU as a ternary quadratic program and present a randomized approximation algorithm based on the complex semidefinite programming relaxation technique.
AB - We consider the max hypergraph 3-cut problem with limited unbalance (MH3C-LU). The objective is to divide the vertex set of an edge-weighted hypergraph H= (V, E, w) into three disjoint subsets V1, V2, and V3 such that the sum of edge weights cross different parts is maximized subject to | | Vi| - | Vl| | ≤ B (∀ i≠ l∈ { 1 , 2 , 3 }) for a given parameter B. This problem is NP-hard because it includes some well-known problems like the max 3-section problem and the max 3-cut problem as special cases. We formulate the MH3C-LU as a ternary quadratic program and present a randomized approximation algorithm based on the complex semidefinite programming relaxation technique.
KW - Approximation algorithm
KW - Complex semidefinite programming
KW - Max hypergraph 3-cut
KW - Randomized algorithm
UR - https://www.scopus.com/pages/publications/85131827032
U2 - 10.1007/s10898-022-01183-7
DO - 10.1007/s10898-022-01183-7
M3 - 文章
AN - SCOPUS:85131827032
SN - 0925-5001
VL - 87
SP - 917
EP - 937
JO - Journal of Global Optimization
JF - Journal of Global Optimization
IS - 2-4
ER -