Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?

Subhash Khot Guy Kindler Elchanan Mossel Ryan O'Donnell

Published in: FOCS (2004)

Keyphrases

max cut
optimal solution
np hard
constraint satisfaction problems
dynamic programming
worst case
approximation algorithms
planar graphs
orders of magnitude