Indexed by:
Abstract:
We present a unified semidefinite programming hierarchies rounding approximation algorithm for a class of maximum graph bisection problems with improved approximation ratios. Under the above algorithmic framework, we show that the approximation ratios of MAX-n/2-CUT, MAX-n/2-DENSE-SUBGRAPH, and MAX-n/ 2-VERTEX-COVER are equal to those of MAX-n/2-UNCUT, MAX-n/2-DIRECTED-CUT, and MAX-n/2-DIRECTED-UNCUT, respectively.
Keyword:
Reprint Author's Address:
Email:
Source :
JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN: 1382-6905
Year: 2015
Issue: 1
Volume: 29
Page: 53-66
1 . 0 0 0
JCR@2022
ESI Discipline: MATHEMATICS;
ESI HC Threshold:82
JCR Journal Grade:2
CAS Journal Grade:3
Cited Count:
WoS CC Cited Count: 7
SCOPUS Cited Count: 6
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 9
Affiliated Colleges: