This work investigates ways in which an algorithm can improve its expected performance by fine-tuning itself automatically, with respect to an arbitrary and unknown input distribution. We give such self-improving algorithms for sorting and for computing Delaunay triangulations. Each algorithm begins with a training phase during which it adjusts itself to the input distribution, followed by a stationary regime in which the algorithm settles to its optimized incarnation. We show that in both cases, in the stationary regime, the algorithms run as fast as possible.
Joint work with Nir Alon, Bernard Chazelle, Ding Liu, C. Seshadhri, and Wolfgang Mulzer.