TY - GEN
T1 - Local max-cut in smoothed polynomial time
AU - Angel, Omer
AU - Bubeck, Sébastien
AU - Peres, Yuval
AU - Wei, Fan
N1 - Funding Information:
We are grateful to Constantinos Daskalakis for bringing this problem to our attention, and for helpful discussions at an early stage of this project. We thank the Bellairs Institute, where this work was initiated. Most of this work was done at Microsoft Research Redmond during the first author's visit and the last author's internship. O. Angel is supported in part by NSERC.
Publisher Copyright:
© 2017 ACM.
PY - 2017/6/19
Y1 - 2017/6/19
N2 - 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öglin 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(loh n) steps where φ is an upper bound on the random edge weight density. 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.
AB - 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öglin 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(loh n) steps where φ is an upper bound on the random edge weight density. 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.
KW - Hopfield network
KW - Max-cut
KW - Nash equilibrium
KW - Polynomial running time
KW - Potential game
KW - Sherrington-Kirkpatrick model
KW - Smoothed analysis
UR - http://www.scopus.com/inward/record.url?scp=85024402415&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85024402415&partnerID=8YFLogxK
U2 - 10.1145/3055399.3055402
DO - 10.1145/3055399.3055402
M3 - Conference contribution
AN - SCOPUS:85024402415
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 429
EP - 437
BT - STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
A2 - McKenzie, Pierre
A2 - King, Valerie
A2 - Hatami, Hamed
PB - Association for Computing Machinery
T2 - 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Y2 - 19 June 2017 through 23 June 2017
ER -