%0 Journal Article %1 chen2019smoothed %A Chen, Xi %A Guo, Chenghao %A Vlatakis-Gkaragkounis, Emmanouil-Vasileios %A Yannakakis, Mihalis %A Zhang, Xinzhi %D 2019 %K complexity computation %T Smoothed complexity of local Max-Cut and binary Max-CSP %U http://arxiv.org/abs/1911.10381 %X 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.

@article{chen2019smoothed, abstract = {We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most $\smash{\phi n^{O(\sqrt{\log n})}}$, 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 $\phi n^{O(\log n)}$ by Etscheid and R\"{o}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.}, added-at = {2020-02-13T11:56:20.000+0100}, author = {Chen, Xi and Guo, Chenghao and Vlatakis-Gkaragkounis, Emmanouil-Vasileios and Yannakakis, Mihalis and Zhang, Xinzhi}, biburl = {https://www.bibsonomy.org/bibtex/281da5d6ae4b5b0f246eccbc4b309cabe/kirk86}, description = {[1911.10381] Smoothed complexity of local Max-Cut and binary Max-CSP}, interhash = {8fd698975708f728c9e070f2f6eb0788}, intrahash = {81da5d6ae4b5b0f246eccbc4b309cabe}, keywords = {complexity computation}, note = {cite arxiv:1911.10381}, timestamp = {2020-02-13T11:56:20.000+0100}, title = {Smoothed complexity of local Max-Cut and binary Max-CSP}, url = {http://arxiv.org/abs/1911.10381}, year = 2019 }