Document Open Access Logo

Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut

Authors Amey Bhangale, Subhash Khot

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2020.9.pdf
  • Filesize: 0.72 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Simultaneous CSPs
  • Unique Games hardness
  • Max-Cut

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

A systematic study of simultaneous optimization of constraint satisfaction problems was initiated by Bhangale et al. [ICALP, 2015]. The simplest such problem is the simultaneous Max-Cut. Bhangale et al. [SODA, 2018] gave a .878-minimum approximation algorithm for simultaneous Max-Cut which is almost optimal assuming the Unique Games Conjecture (UGC). For single instance Max-Cut, Goemans-Williamson [JACM, 1995] gave an α_GW-approximation algorithm where α_GW ≈ .87856720... which is optimal assuming the UGC.
It was left open whether one can achieve an α_GW-minimum approximation algorithm for simultaneous Max-Cut. We answer the question by showing that there exists an absolute constant ε₀ ≥ 10^{-5} such that it is NP-hard to get an (α_GW- ε₀)-minimum approximation for simultaneous Max-Cut assuming the Unique Games Conjecture.

Cite As Get BibTex

Amey Bhangale and Subhash Khot. Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.9

Author Details

Amey Bhangale
  • Department of Computer Science and Engineering, University of California, Riverside, CA, USA
Subhash Khot
  • Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, NY, USA

Funding

  • Bhangale, Amey: Research supported by Irit Dinur’s ERC-CoG grant 772839.
  • Khot, Subhash: Supported by the NSF Award CCF-1813438, the Simons Collaboration on Algorithms and Geometry, and the Simons Investigator Award.

Acknowledgements

Our numerical calculations involve minor modifications of the prover code [Austrin et al.], written by [Austrin et al., 2016], which uses interval arithmetic to get a computer generated proof. We are indebted to the authors of [Austrin et al., 2016] for making it available online. We are also thankful to the anonymous reviewers whose comments helped greatly in improving the presentation of the paper.

Supplementary Materials

References

  1. Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Max-bisection analysis - prover code. https://github.com/austrin/max-bisection-analysis/. Accessed: 08-May-2020.
  2. Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Better balance by being biased: A 0.8776-approximation for max bisection. ACM Trans. Algorithms, 13(1):1-27, 2016. URL: https://doi.org/10.1145/2907052.
  3. Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of vertex cover and independent set in bounded degree graphs. Theory of Computing, 7(3):27-43, 2011. URL: https://doi.org/10.4086/toc.2011.v007a003.
  4. Per Austrin and Aleksa Stankovic. Global cardinality constraints make approximating some max-2-csps harder. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, pages 24:1-24:17, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.24.
  5. Amey Bhangale and Subhash Khot. Simultaneous max-cut dictatorship gadget - prover code. https://github.com/asteric7/simultaneous_maxcut_gadget. Accessed: 08-May-2020.
  6. Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva, and Devanathan Thiruvenkatachari. Near-optimal approximation algorithm for simultaneous max-cut. In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 1407-1425, 2018. URL: https://doi.org/10.1137/1.9781611975031.93.
  7. Amey Bhangale, Swastik Kopparty, and Sushant Sachdeva. Simultaneous approximation of constraint satisfaction problems. In Automata, Languages, and Programming - 42nd International Colloquium, (ICALP), Proceedings, Part I, pages 193-205, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_16.
  8. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM Journal on Computing, 39(3):843-873, 2009. URL: https://doi.org/10.1137/07068062X.
  9. Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995. URL: https://doi.org/10.1145/227683.227684.
  10. Venkatesan Guruswami, Johan HÅstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar. Beating the random ordering is hard: Every ordering csp is approximation resistant. SIAM Journal on Computing, 40(3):878-914, 2011. URL: https://doi.org/10.1137/090756144.
  11. Subhash Khot. On the power of unique 2-prover 1-round games. In Proc. 34th Annual ACM symposium on Theory of computing (STOC), pages 767-775. ACM, 2002. URL: https://doi.org/10.1145/509907.510017.
  12. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for max‐cut and other 2‐variable csps? SIAM Journal on Computing, 37(1):319-357, 2007. URL: https://doi.org/10.1137/S0097539705447372.
  13. Elchanan Mossel. Gaussian bounds for noise correlation of functions. Geometric and Functional Analysis, 19(6):1713-1756, 2010. URL: https://doi.org/10.1007/s00039-010-0047-x.
  14. Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. In Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 21-30. IEEE, 2005. URL: https://doi.org/10.1109/SFCS.2005.53.
  15. Henrik Sjögren. Rigorous analysis of approximation algorithms for max 2-csp. Master’s thesis, 2009. Google Scholar
  16. Uri Zwick. Computer assisted proof of optimal approximability results. In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 496-505, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545448.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact