Computer Science Theory Seminar
Karthik Chandrasekaran
University of Illinois
Improving the smoothed complexity of FLIP for max cut problems
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.
Tuesday October 22, 2019 at 4:00 PM in 1325 SEO