1 problem

0 votes0 replies0 views
Three-candidate Plurality is Stablest hardness consequence for MAX-3-CUT
Sharp hardness consequence. For every $\varepsilon>0$ , it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of $\alpha_{3}+\varepsilon$ .
Theoremopenhardness-of-approximation max-3-cut unique-gamesarXiv posted 2 days ago

Three-candidate Plurality is Stablest hardness consequence for MAX-3-CUT