Indexed by:
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-1, V-2, and V-3 such that the sum of edge weights cross different parts is maximized subject to parallel to V-i vertical bar - vertical bar V-l parallel to <= B (for all i not equal l not equal l is an element of{1, 2, 3}) fora 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.
Keyword:
Reprint Author's Address:
Email:
Source :
JOURNAL OF GLOBAL OPTIMIZATION
ISSN: 0925-5001
Year: 2022
Issue: 2-4
Volume: 87
Page: 917-937
1 . 8
JCR@2022
1 . 8 0 0
JCR@2022
ESI Discipline: ENGINEERING;
ESI HC Threshold:49
JCR Journal Grade:2
CAS Journal Grade:3
Cited Count:
WoS CC Cited Count: 2
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 5
Affiliated Colleges: