The speaker for this week’s theory seminar is Xi Chen from Columbia University. As usual, the talk will take place on Friday 4/14 at Levine 307 from 1-2 PM.
Title: Smoothed Complexity of SWAP for Graph Partitioning
Abstract: Many algorithms and heuristics that work well in practice have poor performance under the worst-case analysis, due to delicate pathological instances that one may never encounter. To bridge this theory-practice gap, Spielman and Teng introduced the smoothed analysis framework which can be viewed as a hybrid of the classical worst-case and average-case analyses. Since then, the smoothed analysis of algorithms and problems from combinatorial optimization, among many other areas, has been studied extensively.
In this work, we give the first quasipolynomial upper bound for the smoothed complexity of the SWAP local search algorithm for Graph Partitioning, where one keeps swapping a pair of vertices to improve the cut weight until no such improvement can be made. The same quasipolynomial bound can also be shown to hold on the 2-FLIP algorithm for Max-Cut. Our results are based on an analysis of cycles formed in long sequences of swaps, showing that it is unlikely for every swap in a long sequence to incur a positive but small improvement in the cut weight.
Based on joint work with Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis and Mihalis Yannakakis.