Local Search

Mutsunori Yagiura and Toshihide Ibaraki
Local search is one of the basic methods to find approximate solutions for hard combinatorial optimization problems, in particular those known as NP-hard. In this chapter, we describe a general framework of local search, and then give some numerical results showing how locally optimal solutions are distributed. These provide an intuitive support to the successful applications of local search algorithms to many optimization problems. Various techniques to enhance the ability of local search and some theoretical results are also mentioned.

Key Words: combinatorial optimization problem, local search, distribution of locally optimal solutions

in: P.M. Pardalos and M.G.C. Resende (eds.), Handbook of Applied Optimization, Oxford University Press, 2002, pp. 104-123.

Back to the Paper List