Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions (Q2121499): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: rhalton / rank | |||
Normal rank |
Revision as of 19:26, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions |
scientific article |
Statements
Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions (English)
0 references
4 April 2022
0 references
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.
0 references
computational geometry
0 references
discrepancy
0 references
subset selection
0 references
mixed-integer linear programming
0 references
branch and bound
0 references