LOCAL SEARCH AND THE LOCAL-STRUCTURE OF NP-COMPLETE PROBLEMS

It is shown that certain NP-complete problems (traveling salesman, min-cut graph partitioning, graph coloring, partition and a version of the satisfiability problem) satisfy a difference equation wth respect to a certain neighborhood that is similar to the wave equation of mathematical physics. Using this it is shown that any local optima with respect to these neighborhoods have a cost better than the average cost of all configurations. Also greedy local search when applied to these problems with respect to the specified neighborhoods and started from an arbitrarily poor initial configuration, will reach the average cost in at most O(nL) iterations where n is the problem size and largest cost is at most 2L above the average cost of all configurations.