Self-improving algorithms

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.