Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions (Q2121499)

This article studies the ``star discrepancy subset selection problem'', which can be formulated easily. Given a set of \(n\) points in the \(d\)-dimensional unit cube, find a subset of \(m\) points (where \(m\le n\)) with minimal star discrepancy. The authors show that this selection problem is in fact NP-hard, and introduce algorithmic methods to tackle the selection problem. In particular, a so-called mixed integer linear programming formulation, and a combinatorial branch-and-bound algorithm are studied, and are compared to random subset selection and a greedy construction. The performance of these methods and the discrepancy values of the output sets are analyzed for dimensions two and three, by considering numerical experiments. The results suggest that a suitably selected subset can have a much lower star discrepancy than, e.g., low-discrepancy point sets or points obtained by Latin Hypercube Sampling.