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.
combinatorial optimization problem,
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