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 -