Karthik Chandrasekaran : Improving the smoothed complexity of FLIP for max cut problems

Posted by Will Perkins , part of the Computer Science Theory Seminar.

At

Oct. 22, 2019, 4 p.m.

In

1325 SEO

Abstract

Finding locally optimal solutions for max-cut and max-k-cut are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the run-time of FLIP for max-cut has been studied in the smoothed complexity model. Etscheid and Roglin (2014) showed that the smoothed complexity of FLIP for max-cut in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres, and Wei (2017) showed that the smoothed complexity of FLIP for max-cut in complete graphs is O(φ^5n^15.1), where φ is an upper bound on the random edge-weight density and n is the number of vertices in the input graph. In this talk, I will present an analysis technique that substantially improves the smoothed run-time bound. Our techniques provide a general framework for analyzing FLIP in the smoothed model. We illustrate this general framework by showing that the smoothed complexity of FLIP for max-3-cut in complete graphs is polynomial and for max-k-cut in arbitrary graphs is quasi-polynomial for constant k. Based on joint work with Ali Bibak and Charles Carlson.