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 -