Local Search & the Local Structural of NP-Complete Problems

人们正在研究复杂问题的局部结构。证明了某些NP-完全问题满足一个与数学物理中的波动方程类似的线性差分方程，并由此得到了一些直接的推论。证明了局部搜索算法从任意较差的配置出发，在一定条件下，在O(N)次迭代内收敛到系统的平均费用。研究了该方程的解及其在模拟退火法、Kernighan-Lin搜索法等局部搜索算法分析和设计中的应用。这些技术对内点法的扩展正在开发中。已经提出了关于这些邻域结构的假设，对于这些邻域结构，局部搜索算法通常将是最成功的。为了验证这一假设，目前正在进行几项测试。其中包括一种新的用于旅行商问题的局部搜索算法，与相同邻域大小的现有算法不同，该算法即使在不满足三角形不平等和/或城市之间的距离不对称的情况下也有望成功。

The local structure of complex problems is being studied. It has been shown that certain NP-complete problems satisfy a linear difference equation that is similar to the wave equation of mathematical physics; some immediate consequences of this have already been deduced. It has been proved that local search algorithms starting from an arbitrary poor configuration, under certain conditions, converge to the average cost of the system in O(n) iterations. The solution of the equation and its application to the analysis and design of local search algorithms like simulated annealing and Kernighan-Lin search are being studied. Extensions of these techniques to interior point methods are being developed. A hypothesis has been proposed regarding these neighborhood structures for which local search algorithms will generally be most successful. Several tests are being conducted to verify this hypothesis. These include a new local search algorithm for the traveling salesman problem that, unlike existing algorithms of the same neighborhood size, is expected to be successful even when the triangle inequality is not satisfied and/or the distances between cities are asymmetric.