Smoothed complexity of local max-cut and binary max-CSP
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang · 2020
We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most φ n O(√logn), where n is the number of nodes in the graph and φ is a parameter that measures the magnitude of perturbations applied on its edge weights. This improves the previously best upper bound of φ n O(logn) by Etscheid and Roglin. Our result is based on an analysis of long sequences of flips, which shows that it is very unlikely for every flip in a long sequence to incur a positive but small improvement in the cut weight. We also extend the same upper bound on the smoothed complexity of FLIP to all binary Maximum Constraint Satisfaction Problems.