# Star Discrepancy Subset Selection: Problem Formulation and Efficient Approaches for Low Dimensions

arXiv: https://arxiv.org/abs/2101.07881 · HTML: https://mlsanity.com/paper/2101.07881/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jan 2021.

## Built on by (most cited first, 4 of 4)

- [Message-Passing Monte Carlo: Generating low-discrepancy point sets via Graph Neural Networks](https://mlsanity.com/paper/2405.15059/) (2024)
- [carps: A Framework for Comparing N Hyperparameter Optimizers on M Benchmarks](https://mlsanity.com/paper/2506.06143/) (2025)
- [Flow-based Extremal Mathematical Structure Discovery](https://mlsanity.com/paper/2601.18005/) (2026)
- [Optimizing Kernel Discrepancies via Subset Selection](https://mlsanity.com/paper/2511.02706/) (2025)

## Abstract (arXiv)

Motivated by applications in instance selection, we introduce the star discrepancy subset selection problem, which consists of finding a subset of m out of n points that minimizes the star discrepancy. First, we show that this problem is NP-hard. Then, we introduce a mixed integer linear formulation (MILP) and a combinatorial branch-and-bound (BB) algorithm for the star discrepancy subset selection problem and we evaluate both approaches against random subset selection and a greedy construction on different use-cases in dimension two and three. Our results show that the MILP and BB are efficient in dimension two for large and small m/n ratio, respectively, and for not too large n. However, the performance of both approaches decays strongly for larger dimensions and set sizes. As a side effect of our empirical comparisons we obtain point sets of discrepancy values that are much smaller than those of common low-discrepancy sequences, random point sets, and of Latin Hypercube Sampling. This suggests that subset selection could be an interesting approach for generating point sets of small discrepancy value.