LIPIcs.CCC.2020.9.pdf
- Filesize: 0.72 MB
- 15 pages
Document
Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut
Authors
-
Part of:
Volume:
35th Computational Complexity Conference (CCC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computational Complexity Conference (CCC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-07-17
File
Document Identifiers
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.
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
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.
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)
0PDF Downloads
References
- Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Max-bisection analysis - prover code. https://github.com/austrin/max-bisection-analysis/. Accessed: 08-May-2020.
- 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.
- 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.
- 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.
- Amey Bhangale and Subhash Khot. Simultaneous max-cut dictatorship gadget - prover code. https://github.com/asteric7/simultaneous_maxcut_gadget. Accessed: 08-May-2020.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
-
Henrik Sjögren. Rigorous analysis of approximation algorithms for max 2-csp. Master’s thesis, 2009.
- 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.