Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
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. Copyright © by SIAM.
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
G. Ramalingam
Theoretical Computer Science
Michael D. Moffitt
ICCAD 2009
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum