Local max-cut in smoothed polynomial time

Omer Angel, Sébastien Bubeck, Yuval Peres, Fan Wei

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

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ö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.

Original languageEnglish (US)
Title of host publicationSTOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
EditorsPierre McKenzie, Valerie King, Hamed Hatami
PublisherAssociation for Computing Machinery
Pages429-437
Number of pages9
ISBN (Electronic)9781450345286
DOIs
StatePublished - Jun 19 2017
Externally publishedYes
Event49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada
Duration: Jun 19 2017Jun 23 2017

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F128415
ISSN (Print)0737-8017

Other

Other49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Country/TerritoryCanada
CityMontreal
Period6/19/176/23/17

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Hopfield network
  • Max-cut
  • Nash equilibrium
  • Polynomial running time
  • Potential game
  • Sherrington-Kirkpatrick model
  • Smoothed analysis

Fingerprint

Dive into the research topics of 'Local max-cut in smoothed polynomial time'. Together they form a unique fingerprint.

Cite this