Local Search & the Local Structural of NP-Complete Problems

点击翻译按钮获取中文摘要

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.