Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut.

Amey Bhangale Subhash Khot

Published in: Computational Complexity Conference (2020)

Keyphrases

max cut
np hard
np complete problems
graph model
np complete
planar graphs
graph partitioning
spectral graph
approximation algorithms
bayesian networks
lower bound
decision problems
min max
pairwise
evolutionary algorithm
constraint satisfaction problems