Self-improving algorithms

Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu

Research output: Contribution to conferencePaperpeer-review

12 Scopus citations


We investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an arbitrary, unknown input distribution. We give such self-improving algorithms for sorting and clustering. The highlights of this work: (i) a sorting algorithm with optimal expected limiting running time; and (ii) a k-median algorithm over the Hamming cube with linear expected limiting running time. In all cases, the algorithm begins with a learning phase during which it adjusts itself to the input distribution (typically in a logarithmic number of rounds), followed by a stationary regime in which the algorithm settles to its optimized incarnation.

Original languageEnglish (US)
Number of pages10
StatePublished - 2006
Externally publishedYes
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006


OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Self-improving algorithms'. Together they form a unique fingerprint.

Cite this