Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem
Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem
复制标题
平方欧氏最大割问题的平滑分析
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Heiko Röglin
中科院分区：
文献类型：
--
作者：
M. Etscheid;Heiko Röglin
众所周知，最大割问题的局部搜索算法可能需要指数级的步骤来找到局部最优值，尽管它们通常在实验中很快稳定下来。为了解释这种差异，我们最近分析了简单的局部搜索算法FLIP的平滑分析的框架，其中输入受到少量的随机噪声。我们已经证明，在这个框架中，迭代次数是准多项式的，即，它在nlogn和φ中是多项式有界的，其中n表示节点数，φ是扰动的参数。
It is well-known that local search heuristics for the Maximum-Cut problem can take an exponential number of steps to find a local optimum, even though they usually stabilize quickly in experiments. To explain this discrepancy we have recently analyzed the simple local search algorithm FLIP in the framework of smoothed analysis, in which inputs are subject to a small amount of random noise. We have shown that in this framework the number of iterations is quasi-polynomial, i.e., it is polynomially bounded in nlogn and φ, where n denotes the number of nodes and φ is a parameter of the perturbation.
影响因子：
1.1
作者：
Matthias Englert;Heiko Röglin;Berthold Vöcking
通讯作者：
Matthias Englert;Heiko Röglin;Berthold Vöcking