Local max-cut in smoothed polynomial time
Local max-cut in smoothed polynomial time
复制标题
平滑多项式时间内的局部最大割
DOI：
10.1145/3055399.3055402
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
F. Wei
中科院分区：
文献类型：
--
作者：
Omer Angel;Sébastien Bubeck;Y. Peres;F. Wei
1988年，约翰逊（Johnson），Papadimitriou和Yannakakis写道：“几乎所有的经验证据都将使我们包括在当地最佳解决方案要容易得多，这比解决NP-HARD问题更容易”。这种现象仍然难以捉摸突破性纸，Etscheid和Röglin证明，局部最大切割的平滑复杂性是准多项式的，即，如果随机扰动任意绑定的重量在本文的随机边缘重量密度上。
In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continued to amass, but formal proofs of this phenomenon have remained elusive. A canonical (and indeed complete) example is the local max-cut problem, for which no polynomial time method is known. In a breakthrough paper, Etscheid and Röglin proved that the smoothed complexity of local max-cut is quasi-polynomial, i.e., if arbitrary bounded weights are randomly perturbed, a local maximum can be found in ϕ nO(logn) steps where ϕ is an upper bound on the random edge weight density. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding local optima for max-cut is much easier than solving it.