Self-improving algorithms

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

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

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
Volume40
Issue number2
DOIs
StatePublished - 2011

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

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

Fingerprint

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

Cite this