__
Revision #1 to TR19-148 | 5th June 2020 20:42
__
#### Simultaneous Max-Cut is harder to approximate than Max-Cut

**Abstract:**
A systematic study of simultaneous optimization of constraint satisfaction problems was initiated in [BKS15]. The simplest such problem is the simultaneous Max-Cut. [BKKST18] gave a $.878$-minimum approximation algorithm for simultaneous Max-Cut which is {\em almost optimal} assuming the Unique Games Conjecture (UGC). For a single instance Max-Cut, [GW95] gave an $\alpha_{GW}$-approximation algorithm where $\alpha_{GW}\approx .87856720...$ which is {\em optimal} assuming the UGC.

It was left open whether one can achieve an $\alpha_{GW}$-minimum approximation algorithm for simultaneous Max-Cut. We answer the question by showing that there exists an absolute constant $\varepsilon_0\geq 10^{-5}$ such that it is NP-hard to get an $(\alpha_{GW}- \varepsilon_0)$-minimum approximation for simultaneous Max-Cut assuming the UGC.

**Changes to previous version:**
1. Added figures.

2. Added a link to the prover code that was used to prove a numerical inequality.

3. Fixed minor typos.

__
TR19-148 | 1st November 2019 21:01
__

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

**Abstract:**
A systematic study of simultaneous optimization of constraint satisfaction problems was initiated in [BKS15]. The simplest such problem is the simultaneous Max-Cut. [BKKST18] gave a $.878$-minimum approximation algorithm for simultaneous Max-Cut which is {\em almost optimal} assuming the Unique Games Conjecture (UGC). For a single instance Max-Cut, [GW95] gave an $\alpha_{GW}$-approximation algorithm where $\alpha_{GW}\approx .87856720...$ which is {\em optimal} assuming the UGC.

It was left open whether one can achieve an $\alpha_{GW}$-minimum approximation algorithm for simultaneous Max-Cut. We answer the question by showing that there exists an absolute constant $\varepsilon_0\geq 10^{-5}$ such that it is NP-hard to get an $(\alpha_{GW}- \varepsilon_0)$-minimum approximation for simultaneous Max-Cut assuming the UGC.