Theory of local search

W. Michiels, E.H.L. Aarts, Jan Korst

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

4 Citations (Scopus)
2 Downloads (Pure)


Local search is a widely used method to solve combinatorial optimization problems. As many relevant combinatorial optimization problems are NP-hard, we often may not expect to find an algorithm that is guaranteed to return an optimal solution in a reasonable amount of time, i.e., in polynomial time. Therefore, one often resorts to heuristic methods that return good, suboptimal solutions in reasonable running times. Local search is a heuristic method that is popular for its ability to trade solution quality against computation time. By spending more time, we will generally get better solutions.Well-known examples of local search approaches are iterative improvement, simulated annealing, and tabu search. The performance of local search, in terms of quality or running time, may be investigated empirically, probabilistically, and from a worst-case perspective. In this chapter we focus on the last option. That is, we give provable results on the worst-case performance of local search algorithms. Besides combinatorial optimization problems, the theory discussed in this chapter also finds its application in game theory and computational complexity.

Original languageEnglish
Title of host publicationHandbook of heuristics
EditorsR. Martí, P. Pardalos, M. Resende
Place of PublicationCham
Number of pages41
ISBN (Electronic)978-3-319-07124-4
ISBN (Print)978-3-319-07123-7
Publication statusPublished - 13 Aug 2018


  • Iterative improvement
  • Performance ratio
  • PLS
  • Time complexity


Dive into the research topics of 'Theory of local search'. Together they form a unique fingerprint.

Cite this