Abstract
We show that the smoothed complexity of the FLIP algorithm for local Max-Cut
is at most $n^O(\sqrtn)$, where $n$ is the number of
nodes in the graph and $\phi$ is a parameter that measures the magnitude of
perturbations applied on its edge weights. This improves the previously best
upper bound of $n^O(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.
Users
Please
log in to take part in the discussion (add own reviews or comments).