Loading…
A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
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 1 , V 2 , and V 3 such that the sum of edge weights cross different parts is maximized subject to |...
Saved in:
Published in: | Journal of global optimization 2023-11, Vol.87 (2-4), p.917-937 |
---|---|
Main Authors: | , , , , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | 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
1
,
V
2
, and
V
3
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. |
---|---|
ISSN: | 0925-5001 1573-2916 |
DOI: | 10.1007/s10898-022-01183-7 |