Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut.

Konstantin Makarychev Yury Makarychev Aravindan Vijayaraghavan

Published in: SODA (2014)

Keyphrases

max cut
np complete problems
planar graphs
np complete
graph model
graph coloring
phase transition
graph partitioning
np hard
randomly generated
multiscale
approximate inference
minimum cost
combinatorial problems
min max
timetabling problem