Self-improving algorithms

Nir Ailon, Bernard Chazelle, Kenneth L. Clarkson, Ding Liu, Wolfgang Mulzer, C. Seshadhri

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


We investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an unknown input distribution D. We assume here that D is of product type. More precisely, suppose that we need to process a sequence I1, I2, . . . of inputs I = (x1, x2, . . . , xn) of some fixed length n, where each xi is drawn independently from some arbitrary, unknown distribution Di. The goal is to design an algorithm for these inputs so that eventually the expected running time will be optimal for the input distribution D = πi Di. We give such self-improving algorithms for two problems: (i) sorting a sequence of numbers and (ii) computing the Delaunay triangulation of a planar point set. Both algorithms achieve optimal expected limiting complexity. The algorithms begin with a training phase during which they collect information about the input distribution, followed by a stationary regime in which the algorithms settle to their optimized incarnations.

Original languageEnglish (US)
Pages (from-to)350-375
Number of pages26
JournalSIAM Journal on Computing
Issue number2
StatePublished - 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


  • Average case analysis
  • Delaunay triangulation
  • Low entropy
  • Sorting


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

Cite this