Smoothed Analysis of Algorithms and Heuristics

Daniel A. Spielman, Shang-Hua TengCambridge 2006 · DOI · OpenAlex

Abstract

In this paper, we survey some recent progress in the smoothed analysis of algorithms and heuristics in mathematical programming, combinatorial optimization, computational geometry, and scientific computing. Our focus will be more on problems and results rather than on proofs. We discuss several perturbation models used in smoothed analysis for both continuous and discrete inputs. Perhaps more importantly, we present a collection of emerging open questions as food for thought in this field.
BibTeX
@inproceedings{spielman2006smoothed,
  author = {Daniel A. Spielman and Shang-Hua Teng},
  title = {{Smoothed Analysis of Algorithms and Heuristics}},
  booktitle = {Cambridge},
  year = {2006},
  doi = {10.1017/cbo9780511721571.010},
}

Loading related content...

Figure