Local search and the local structure of NP-complete problems

Local search and the local structure of NP-complete problems

0.00 Avg rating0 Votes
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:
Keywords: NP-complete
Abstract:

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(nL) iterations where n is the problem size and largest cost is at most 2’L above the average cost of all configurations.

Reviews

Required fields are marked *. Your email address will not be published.