ABSTRACT
Local search is concerned with the design and analysis of a special class of algorithms that can find approximate solutions for hard combinatorial optimization problems. Solving a combinatorial optimization problem amounts to finding an optimal solution among a finite or countably infinite number of alternative solutions. Here, optimality is related to some cost criterion that provides a quantitative measure of the quality of each solution. This area of discrete mathematics is of great practical use and has attracted much attention over the years. For extensive and detailed introductions in the field the reader is referred to the books by Aarts and Lenstra, Nemhauser and Wolsey (1988), Papadimitriou and Steiglitz (1982), and Schrijver (1986). An annotated bibliography of the field is given by O'Heigeartaigh, Lenstra, and Rinnooy Kan (1985). Many combinatorial optimization problems belong to the class of NP-hard problems; see Garey and Johnson (1979). It is generally believed that these problems cannot be solved to optimality within polynomially bounded computation times. This property has led to a variety of solution methods, which can be distinguished using the following criteria:
