Approximate Local Search in Combinatorial Optimization

Local search algorithms for combinatorial optimization problems are generally of pseudopolynomial running time, and polynomial-time algorithms are not often known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of amp;#949;-local optimality and show that, for every amp;#949; gt; 0, an amp;#949;-local optimum can be identified in time polynomial in the problem size and 1/amp;#949; whenever the corresponding neighborhood can be searched in polynomial time. If the neighborhood can be searched in polynomial time for a amp;#948;-local optimum, a variation of our main algorithm produces a (amp;#948; + amp;#949;)-local optimum in time polynomial in the problem size and 1/amp;#949;. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if the problem of determining a better neighbor in an exact neighborhood has a fully polynomial-time approximation scheme