@inproceedings{7066357562ff44119c38b9d2c04f2855,
title = "Simultaneous Max-Cut is harder to approximate than Max-Cut",
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 ε0 > 10−5 such that it is NP-hard to get an (αGW − ε0)-minimum approximation for simultaneous Max-Cut assuming the Unique Games Conjecture.",
keywords = "Max-Cut, Simultaneous CSPs, Unique Games hardness",
author = "Amey Bhangale and Subhash Khot",
note = "Publisher Copyright: {\textcopyright} Amey Bhangale and Subhash Khot; licensed under Creative Commons License CC-BY 35th Computational Complexity Conference (CCC 2020).; 35th Computational Complexity Conference, CCC 2020 ; Conference date: 28-07-2020 Through 31-07-2020",
year = "2020",
month = jul,
day = "1",
doi = "10.4230/LIPIcs.CCC.2020.9",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Shubhangi Saraf",
booktitle = "35th Computational Complexity Conference, CCC 2020",
}