Name
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 $\mathcal{D}$. We assume here that $\mathcal{D}$ is of product type. More precisely, suppose that we need to process a sequence $I_1,I_2,\ldots$ of inputs $I=(x_1,x_2,\ldots,x_n)$ of some fixed length $n$, where each $x_i$ is drawn independently from some arbitrary, unknown distribution $\mathcal{D}_i$. The goal is to design an algorithm for these inputs so that eventually the expected running time will be optimal for the input distribution $\mathcal{D}=\prod_i\mathcal{D}_i$. 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1137/090766437 | SIAM J. Comput. |
Keywords | DocType | Volume |
expected performance,unknown input distribution,product type,unknown distribution,optimized incarnation,delaunay triangulation,planar point set,input distribution,self-improving algorithm,self-improving algorithms,fixed length,sorting | Journal | 40 |
Issue | ISSN | Citations |
2 | SIAM Journal on Computing (SICOMP), 40(2), 2011, pp. 350-375 | 10 |
PageRank | References | Authors |
0.47 | 28 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nir Ailon | 1 | 1114 | 70.74 |
| Bernard Chazelle | 2 | 6848 | 814.04 |
| Kenneth L. Clarkson | 3 | 2516 | 332.21 |
| Ding Liu | 4 | 281 | 16.53 |
| Wolfgang Mulzer | 5 | 257 | 36.08 |
| C. Seshadhri | 6 | 936 | 61.33 |