Smoothed complexity of local max-cut and binary max-CSP
Smoothed complexity of local max-cut and binary max-CSP
复制标题
局部最大割和二值最大 CSP 的平滑复杂度
DOI：
10.1145/3357713.3384325
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zhang, Xinzhi
中科院分区：
文献类型：
--
作者：
Chen, Xi;Guo, Chenghao;Vlatakis-Gkaragkounis, Emmanouil V.;Yannakakis, Mihalis;Zhang, Xinzhi
证明了局部最大割的Flip算法的平滑复杂度至多为φno(√logn)，其中φ是图中节点的个数，是衡量边权上扰动大小的参数。这改进了以前由Etscheid和Roglin得到的φNO(LogN)的最佳上界。我们的结果是基于对长序列翻转的分析，这表明在长序列中的每一次翻转都不太可能在减重方面产生积极但微小的改善。我们还将Flip的光滑复杂性的相同上界推广到所有二元最大约束满足问题。
We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most φnO(√logn), wherenis 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 φnO(logn)by Etscheid and Roglin. 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.
登录
查看更多内容
（几乎）完全解决局部最大割的复杂性
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
提高 FLIP 最大割问题的平滑复杂度
影响因子：
1.3
作者：
Bibak, Ali;Carlson, Charles;Chandrasekaran, Karthekeyan
通讯作者：
Chandrasekaran, Karthekeyan
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