Heuristics

Local search. There are no guarantees of being close to optimal, but often works well in practice. This is better than Approximation Algorithms because we don’t need to define a threshold of how close to optimality we need to be.

There is an approximation hierarchy:

1. No finite approximation
2. Finite approximation
3. Arbitrarily good approximation (polynomial time approximation scheme)

Local Search

Let s be any initial solution
 
while there is a solution s' in the "neighborhood" of s for which cost(s') < cost(s):
    replace s by s'
return s