Article ID: | iaor19931162 |
Country: | Netherlands |
Volume: | 12 |
Issue: | 4 |
Start Page Number: | 235 |
End Page Number: | 243 |
Publication Date: | Oct 1992 |
Journal: | Operations Research Letters |
Authors: | Grover Lov K. |
Keywords: | NP-complete |
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 with 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(