Local Search

Mutsunori Yagiura and Toshihide Ibaraki

ABSTRACT

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