TY - GEN
T1 - Local max-cut in smoothed polynomial time
AU - Angel, Omer
AU - Bubeck, Sébastien
AU - Peres, Yuval
AU - Wei, Fan
N1 - 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 -