Smoothed complexity of local Max-Cut and binary Max-CSP
share
We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most ϕ n^O(√(log n)), 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(log n) by Etscheid and Röglin. 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.
READ FULL TEXT