@article{angel2017local,
author = {Angel, Omer and Bubeck, Sébastien and Peres, Yuval and Wei, Fan},
title = {Local Max-Cut In Smoothed Polynomial Time},
year = {2017},
month = {April},
abstract = {In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continued to amass, but formal proofs of this phenomenon have remained elusive. A canonical (and indeed complete) example is the local max-cut problem, for which no polynomial time method is known. In a breakthrough paper, Etscheid and R\"oglin proved that the smoothed complexity of local max-cut is quasi-polynomial, i.e., if arbitrary bounded weights are randomly perturbed, a local maximum can be found in nO(logn) steps. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding local optima for max-cut is much easier than solving it.},
url = {http://approjects.co.za/?big=en-us/research/publication/local-max-cut-smoothed-polynomial-time/},
}