Local max-cut in smoothed polynomial time

2016/10/16 by Angel, Omer, Bubeck, Sébastien, Peres, Yuval +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1610.04807

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 n^{O(log n)} 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.

Cited by

• Smoothed Analysis of Online Metric Problems

Related

• Settling the complexity of local max-cut (almost) completely
• Smoothed complexity of local Max-Cut and binary Max-CSP
• Improving the smoothed complexity of FLIP for max cut problems
• Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
• Local Max-Cut on Sparse Graphs