A0387
Title: Relaxed greedy packing for nested space-filling designs
Authors: Luc Pronzato - CNRS - Universite Cote d'Azur (France) [presenting]
Abstract: Various relaxations of the greedy packing algorithm are considered for the construction of nested designs on a given compact set $X$, with a guaranteed lower bound on packing and covering efficiency for each design size. Relaxation can include randomness. Although the stochastic properties of the nested random designs that are generated are much more difficult to study than those of designs generated by the now popular determinant point processes, (i) the construction of a design $\{x_1,\ldots,x_n\}$ of arbitrary size $n$ is straightforward, (ii) guaranteed packing and covering performance is available for all sub-designs $\{x_1,\ldots,x_k\}$, $k\leq n$. When $X$ is the hypercube $[0,1]^d$, projections onto canonical subspaces can be taken into account, random Latin hypercubes being special cases. Relaxation can correspond to greedy minimization of the energy for a positive definite kernel $K$, which defines a correlation function for a random process on $X$, with Mat\'ern kernels as special cases. It is shown that when the correlation length tends to zero fast enough, the sequence of nested designs is asymptotically 50\% packing and covering optimal. Finally, greedy packing tends to choose many design points on the boundary of $X$. Relaxation can correspond to boundary avoidance, which in practice is shown to improve covering performance.
