Simultaneous Max-Cut is harder to approximate than Max-Cut

Amey Bhangale, Subhash Khot

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 > 105 such that it is NP-hard to get an (αGW − ε0)-minimum approximation for simultaneous Max-Cut assuming the Unique Games Conjecture.

Original languageEnglish (US)
Title of host publication35th Computational Complexity Conference, CCC 2020
EditorsShubhangi Saraf
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771566
DOIs
StatePublished - Jul 1 2020
Event35th Computational Complexity Conference, CCC 2020 - Virtual, Online, Germany
Duration: Jul 28 2020Jul 31 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume169
ISSN (Print)1868-8969

Conference

Conference35th Computational Complexity Conference, CCC 2020
CountryGermany
CityVirtual, Online
Period7/28/207/31/20

Keywords

  • Max-Cut
  • Simultaneous CSPs
  • Unique Games hardness

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Simultaneous Max-Cut is harder to approximate than Max-Cut'. Together they form a unique fingerprint.

Cite this