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-cutproblem for which no polynomial time method is known. In a breakthrough paper, Etscheid and R{“o}glin proved that the {em smoothed} complexity of local max-cut is quasi polynomial. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding locally optimal solutions for max-cut is much easier than solving it.
This is a joint work with Omer Angel, Sebastien Bubeck, and Yuval Peres.
Time
2017-03-28 14:00 ~ 15:00Speaker
Fan Wei, Stanford UniversityRoom
Room 308,School of Information Management & Engineering, Shanghai University of Finance & Economics
