A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis

Jian Sun; Zan Bo Zhang; Yannan Chen; Deren Han; Donglei Du; Xiaoyan Zhang

doi:10.1007/s10898-022-01183-7

A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis

Jian Sun
, Zan Bo Zhang
, Yannan Chen
, Deren Han
, Donglei Du
, Xiaoyan Zhang^*

^*Corresponding author for this work

School of Mathematical Sciences

Beijing University of Technology
Guangdong University of Finance & Economics
South China Normal University
University of New Brunswick
Nanjing Normal University

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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 V₁, V₂, and V₃ such that the sum of edge weights cross different parts is maximized subject to | | V_i| - | V_l| | ≤ 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.

Original language	English
Pages (from-to)	917-937
Number of pages	21
Journal	Journal of Global Optimization
Volume	87
Issue number	2-4
DOIs	https://doi.org/10.1007/s10898-022-01183-7
State	Published - Nov 2023

Keywords

Approximation algorithm
Complex semidefinite programming
Max hypergraph 3-cut
Randomized algorithm

Access to Document

10.1007/s10898-022-01183-7

Cite this

@article{cc18b2bc6d644f35a5f54cb6057f02ed,

title = "A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis",

abstract = "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.",

keywords = "Approximation algorithm, Complex semidefinite programming, Max hypergraph 3-cut, Randomized algorithm",

author = "Jian Sun and Zhang, \{Zan Bo\} and Yannan Chen and Deren Han and Donglei Du and Xiaoyan Zhang",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2023",

month = nov,

doi = "10.1007/s10898-022-01183-7",

language = "英语",

volume = "87",

pages = "917--937",

journal = "Journal of Global Optimization",

issn = "0925-5001",

publisher = "Springer Netherlands",

number = "2-4",

}

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

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 -

A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this