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

DOI10.1016/j.jco.2022.101645zbMath1494.11063arXiv2101.07881MaRDI QIDQ2121499

François Clément, Carola Doerr, Luís Paquete

Publication date: 4 April 2022

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2101.07881

zbMATH Keywords

branch and bound; subset selection; discrepancy; computational geometry; mixed-integer linear programming

Mathematics Subject Classification ID

65C05: Monte Carlo methods

65D32: Numerical quadrature and cubature formulas

65D30: Numerical integration

11K38: Irregularities of distribution, discrepancy

11J71: Distribution modulo one

Uses Software

• rhalton
• sobol.cc
• Algorithm 247

Cites Work

• Unnamed Item
• Unnamed Item
• Constructing Sobol Sequences with Better Two-Dimensional Projections
• Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
• Fibonacci sets and symmetrization in discrepancy theory
• Good permutations for deterministic scrambled Halton sequences in terms of \(L_2\)-discrepancy
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• On the small ball inequality in all dimensions
• Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
• An improved low-discrepancy sequence for multidimensional quasi-Monte Carlo integration
• On optimal extreme-discrepancy point sets in the square
• A method for exact calculation of the discrepancy of low-dimensional finite point sets. I
• The design and analysis of computer experiments.
• Discrepancy and convex programming
• Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
• A lower bound for the discrepancy of a random point set
• A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting
• A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Output from a Computer Code
• MONTE CARLO METHODS FOR SOLVING MULTIVARIABLE PROBLEMS
• Discrépance de suites associées à un système de numération (en dimension s)
• The inverse of the star-discrepancy depends linearly on the dimension
• Probabilistic Lower Bounds for the Discrepancy of Latin Hypercube Samples
• Calculation of Discrepancy Measures and Applications
• Probabilistic discrepancy bound for Monte Carlo point sets
• On the distribution of points in a cube and the approximate evaluation of integrals
• Irregularities of distribution, VII