On the complexity of local search
On the complexity of local search
复制标题
论本地搜索的复杂性
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
M. Yannakakis
中科院分区：
文献类型：
--
作者：
C. Papadimitriou;A. Schäffer;M. Yannakakis
我们证明了一些复杂性结果的计算范式的局部最优性。我们的主要结果是：（a）在Lin-Kernighan启发式算法下，旅行商问题的局部最优解是PLS完全的。(b)在Hopfield模式/中寻找神经网络的稳定配置是PLS完全的。(c)我们证明了一系列简单的未加权局部最优问题是P-完全的。(d)我们介绍了一个一般的框架，建立指数最坏情况下的边界局部优化算法。(e)我们表明，局部搜索问题成为PSPACE-完全的，如果我们坚持局部最优返回可达到从一个给定的初始解的局部改进。
We prove a number of complexity results on the computational paradigm of local op-timality. Our main results are these: (a) Finding a local optimum under the Lin-Kernighan heuristic for the traveling salesman problemis PLS-complete. (b) Finding stable configurations in neural networks in the Hopfield mode/is PLS-complete. (c) We show that a host of simple unweighted local optimality problems are P-complete. (d) We introduce a general framework for establishing exponential worst-case bounds for local optimization heuristics. (e) And we show that local search problems become PSPACE-complete if we insist that the local optimum returned be attainable by local improvements from a given initial solution.