Name
Abstract | ||
|---|---|---|
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 − o(1) for this problem (and an approximation factor of 1/2 + εk in the unweighted case, where εk → 0 as k → ∞).
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].
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.5555/3174304.3175398 | SODA '18: Symposium on Discrete Algorithms
New Orleans
Louisiana
January, 2018 |
DocType | Volume | ISBN |
Journal | abs/1801.04497 | 978-1-61197-503-1 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amey Bhangale | 1 | 10 | 6.71 |
| Subhash Khot | 2 | 2064 | 112.51 |
| Swastik Kopparty | 3 | 384 | 32.89 |
| Sushant Sachdeva | 4 | 171 | 16.90 |
| Devanathan Thiruvenkatachari | 5 | 0 | 1.69 |