Smoothed Analysis of Local Search

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


Local search is a powerful paradigm for finding good solutions to intractable combinatorial optimization problems. However, for many local search heuristics there exist worst-case instances on which they are extremely slow or provide solutionsthat are far from optimal. Smoothed analysis is a semi-random input model that has been invented to bridge the gap between poor worst-case and good empirical performance of algorithms. In smoothed analysis, an adversary picks an arbitrary input, which is then slightly randomly perturbed. In particular, smoothed analysis has been applied successfullyto local search algorithms in a variety of cases. We use the 2-opt heuristic for the traveling salesman problem and the k-means method for clustering as examples to explain how local search heuristics can be analyzed in the framework of smoothed analysis. For both algorithm, as for many other local search algorithms, the worst-case running time is exponential in the input size, but polynomial in the framework of smoothed analysis.
Original languageEnglish
Title of host publicationBeyond the Worst-Case Analysis of Algorithms
EditorsTim Roughgarden
PublisherCambridge University Press
Number of pages24
ISBN (Electronic)9781108637435
Publication statusPublished - Dec 2020


Dive into the research topics of 'Smoothed Analysis of Local Search'. Together they form a unique fingerprint.

Cite this