Computational bounds for local search in combinatorial optimization

The results related to finding local optima in combinatorial optimization are overviewed. The class of polynomial-time local search problems (class PLS) is considered. By analogy with Cook's theorem, the existence of most complicated problems in this class is established. The number of steps in local descent algorithms is estimated in the worst and average cases. The local search determination of exact and approximate solutions with guaranteed error bounds is discussed.