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

DOI10.1016/j.jco.2022.101645zbMath1494.11063arXiv2101.07881OpenAlexW4220854895MaRDI 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 boundsubset selectiondiscrepancycomputational geometrymixed-integer linear programming

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical quadrature and cubature formulas (65D32) Numerical integration (65D30) Irregularities of distribution, discrepancy (11K38) Distribution modulo one (11J71)

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