Improving the smoothed complexity of FLIP for max cut problems

DOI10.1137/1.9781611975482.55MaRDI QIDQ5236239zbMATH OpenOpenAlexFDO

Authors Ali Bibak, Charles Carlson, Karthekeyan Chandrasekaran

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.05665

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: Finding locally optimal solutions for max-cut and max-$k$-cut are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the run-time of FLIP has been studied in the smoothed complexity framework. Etscheid and R"{o}glin showed that the smoothed complexity of FLIP for max-cut in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres, and Wei showed that the smoothed complexity of FLIP for max-cut in complete graphs is $O(ph{i}^5{n}^{15.1})$, where $phi$ is an upper bound on the random edge-weight density and $n$ is the number of vertices in the input graph. While Angel et al.'s result showed the first polynomial smoothed complexity, they also conjectured that their run-time bound is far from optimal. In this work, we make substantial progress towards improving the run-time bound. We prove that the smoothed complexity of FLIP in complete graphs is $O(phi{n}^{7.83})$. Our results are based on a carefully chosen matrix whose rank captures the run-time of the method along with improved rank bounds for this matrix and an improved union bound based on this matrix. In addition, our techniques provide a general framework for analyzing FLIP in the smoothed framework. We illustrate this general framework by showing that the smoothed complexity of FLIP for max-$3$-cut in complete graphs is polynomial and for max-$k$-cut in arbitrary graphs is quasi-polynomial. We believe that our techniques should also be of interest towards addressing the smoothed complexity of FLIP for max-$k$-cut in complete graphs for larger constants $k$.

Recommendations

• Settling the complexity of local max-cut (almost) completely
• Smoothed analysis of the squared Euclidean maximum-cut problem
• Local max-cut in smoothed polynomial time
• Integer Linear Programs and Local Search for Max-Cut
• Smoothed analysis of local search for the maximum-cut problem

Cited in

(8)

• Settling the complexity of local max-cut (almost) completely
• Smoothed analysis of the squared Euclidean maximum-cut problem
• Local max-cut in smoothed polynomial time
• Improving the Smoothed Complexity of FLIP for Max Cut Problems
• scientific article; zbMATH DE number 7204399 (Why is no real title available?)
• Smoothed complexity of local max-cut and binary max-CSP
• Minimum stable cut and treewidth
• Settling the complexity of Nash equilibrium in congestion games

This page was built for publication: Improving the smoothed complexity of FLIP for max cut problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236239)