TY - GEN
T1 - Near-optimal approximation algorithm for simultaneous Max-cut
AU - Bhangale, Amey
AU - Khot, Subhash
AU - Kopparty, Swastik
AU - Sachdeva, Sushant
AU - Thiruvenkatachari, Devanathan
N1 - Publisher Copyright:
© Copyright 2018 by SIAM.
PY - 2018
Y1 - 2018
N2 - In the simultaneous Max-Cut problem, we are given k weighted graphs on the same set of n vertices, and the goal is to find a cut of the vertex set so that the minimum, over the k graphs, of the cut value is as large as possible. Previous work [BKS15] gave a polynomial time algorithm which achieved an approximation factor of 1-2- op1q for this problem (and an approximation factor of 1-2 + ϵk in the unweighted case, where "k Ñ 0 as k Ñ 8). In this work, we give a polynomial time approximation algorithm for simultaneous Max-Cut with an approximation factor of 0:8780 (for all constant k). The natural SDP formulation for simultaneous Max-Cut was shown to have an integrality gap of 1-2+ϵk in [BKS15]. In achieving the better approximation guarantee, we use a stronger Sum-of-Squares hierarchy SDP relaxation and a rounding algorithm based on Raghavendra-Tan [RT12], in addition to techniques from [BKS15].
AB - In the simultaneous Max-Cut problem, we are given k weighted graphs on the same set of n vertices, and the goal is to find a cut of the vertex set so that the minimum, over the k graphs, of the cut value is as large as possible. Previous work [BKS15] gave a polynomial time algorithm which achieved an approximation factor of 1-2- op1q for this problem (and an approximation factor of 1-2 + ϵk in the unweighted case, where "k Ñ 0 as k Ñ 8). In this work, we give a polynomial time approximation algorithm for simultaneous Max-Cut with an approximation factor of 0:8780 (for all constant k). The natural SDP formulation for simultaneous Max-Cut was shown to have an integrality gap of 1-2+ϵk in [BKS15]. In achieving the better approximation guarantee, we use a stronger Sum-of-Squares hierarchy SDP relaxation and a rounding algorithm based on Raghavendra-Tan [RT12], in addition to techniques from [BKS15].
UR - http://www.scopus.com/inward/record.url?scp=85045562479&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045562479&partnerID=8YFLogxK
U2 - 10.1137/1.9781611975031.93
DO - 10.1137/1.9781611975031.93
M3 - Conference contribution
AN - SCOPUS:85045562479
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1407
EP - 1425
BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
A2 - Czumaj, Artur
PB - Association for Computing Machinery
T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Y2 - 7 January 2018 through 10 January 2018
ER -