On the Hardness of Approximating Max k-Cut and Its Dual.

Viggo Kann Sanjeev Khanna Jens Lagergren Alessandro Panconesi

Published in: ISTCS (1996)

Keyphrases

np hard
worst case
computational complexity
np complete
machine learning
np hardness
data sets
databases
search space
information theoretic
phase transition
learning theory