Improving the Smoothed Complexity of FLIP for Max Cut Problems
Improving the Smoothed Complexity of FLIP for Max Cut Problems
复制标题
提高 FLIP 最大割问题的平滑复杂度
DOI：
10.1145/3454125
复制
发表时间：
2021
影响因子：
1.3
通讯作者：
Chandrasekaran, Karthekeyan
中科院分区：
文献类型：
--
作者：
Bibak, Ali;Carlson, Charles;Chandrasekaran, Karthekeyan
寻找局部最优解formax - cutandmax -k- cut是众所周知的pls完全问题。寻找这种局部最优解的一种本能的方法是FLIP方法。尽管FLIP在最坏情况下需要指数级的时间，但在实际情况下，它往往会很快终止。为了解释这种差异，我们在平滑复杂度框架下研究了FLIP的运行时间。Etscheid和Röglin （ACM Transactions on Algorithms, 2017）表明，FLIP格式切割任意图的平滑复杂度是拟多项式的。Angel, Bubeck, Peres, and Wei （STOC, 2017）表明，FLIP格式-剪切完全图的平滑复杂度为（OΦ5n15.1），其中Φ为随机边权密度的上界，Φ为输入图中的顶点数。虽然Angel， Bubeck， Peres和Wei的结果显示了第一个多项式平滑复杂性，但他们也推测他们的运行时间界限远非最佳。在这项工作中，我们在改进运行时界限方面取得了实质性进展。我们证明了FLIP格式切割完全图的光滑复杂度isO（Φn7.83）。我们的结果基于一个精心选择的矩阵，该矩阵的秩捕获了方法的运行时间，以及该矩阵的改进秩界和基于该矩阵的改进联合界。此外，我们的技术为在平滑框架中分析FLIP提供了一个通用框架。我们通过证明FLIP forMAX-3-CUTin完全图的光滑复杂度是多项式，forMAX-k-CUTin任意图的光滑复杂度是拟多项式来说明这个一般框架。我们相信我们的技术也应该对展示更大常数的FLIP forMAX-k-CUTin完全图的光滑多项式复杂度感兴趣。
Finding locally optimal solutions forMAX-CUTandMAX-k-CUTare 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öglin (ACM Transactions on Algorithms, 2017) showed that the smoothed complexity of FLIP formax-cutin arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres, and Wei (STOC, 2017) showed that the smoothed complexity of FLIP formax-cutin complete graphs is (OΦ5n15.1), where Φ is an upper bound on the random edge-weight density and Φ is the number of vertices in the input graph.While Angel, Bubeck, Peres, and Wei’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 toward improving the run-time bound. We prove that the smoothed complexity of FLIP formax-cutin complete graphs isO(Φn7.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 forMAX-3-CUTin complete graphs is polynomial and forMAX-k-CUTin arbitrary graphs is quasi-polynomial. We believe that our techniques should also be of interest toward showing smoothed polynomial complexity of FLIP forMAX-k-CUTin complete graphs for larger constantsk.
登录
查看更多内容
（几乎）完全解决局部最大割的复杂性
DOI：
10.1007/978-3-642-22006-7_15
发表时间：
2010
期刊：
2011 Eighth International Conference on Quantitative Evaluation of SysTems
影响因子：
--
作者：
Robert Elsässer;Tobias Tscheuschner
通讯作者：
Tobias Tscheuschner
切分、政党归属和可满足性博弈中的近似纯纳什均衡
DOI：
--
发表时间：
2010
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
Anand Bhalgat;T. Chakraborty;S. Khanna
通讯作者：
S. Khanna
DOI：
--
发表时间：
2015
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
M. Etscheid;Heiko Röglin
通讯作者：
Heiko Röglin
DOI：
10.1145/3011870
发表时间：
2017
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
M. Etscheid;Heiko Röglin
通讯作者：
Heiko Röglin
平滑多项式时间内的局部最大割
DOI：
10.1145/3055399.3055402
发表时间：
2016
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Omer Angel;Sébastien Bubeck;Y. Peres;F. Wei
通讯作者：
F. Wei