Smoothed Analysis of Local Search for the Maximum-Cut Problem
Smoothed Analysis of Local Search for the Maximum-Cut Problem
复制标题
最大割问题局部搜索的平滑分析
DOI：
10.1145/3011870
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Heiko Röglin
中科院分区：
文献类型：
--
作者：
M. Etscheid;Heiko Röglin
即使本地搜索启发式方法在实践中选择了许多经过深入研究的优化问题，但其中大多数在最坏的情况下表现不佳。采取指数数量的步骤终止，计算本地最佳的问题是PLS完整的，以缩小理论和实践之间的差距平滑分析的框架，其中输入会受到少量的随机噪声。节点和φ表示扰动参数。
Even though local search heuristics are the method of choice in practice for many well-studied optimization problems, most of them behave poorly in the worst case. This is, in particular, the case for the Maximum-Cut Problem, for which local search can take an exponential number of steps to terminate and the problem of computing a local optimum is PLS-complete. To narrow the gap between theory and practice, we study local search for the Maximum-Cut Problem in the framework of smoothed analysis in which inputs are subject to a small amount of random noise. We show that the smoothed number of iterations is quasi-polynomial, that is, it is bounded from above by a polynomial in nlog n and φ, where n denotes the number of nodes and φ denotes the perturbation parameter. This shows that worst-case instances are fragile, and it is a first step in explaining why they are rarely observed in practice.
影响因子：
1.1
作者：
Matthias Englert;Heiko Röglin;Berthold Vöcking
通讯作者：
Matthias Englert;Heiko Röglin;Berthold Vöcking