A Randomized Algorithm Based on Threshold Accepting to Approximate the Star Discrepancy

Abstract

We present a new algorithm for estimating the star discrepancy of arbitrary point sets. Similar to the algorithm for discrepancy approximation of Winker and Fang [SIAM J. Numer. Anal. 34 (1997), 2028--2042] it is based on the optimization algorithm threshold accepting. Our improvements include, amongst others, a non-uniform sampling strategy which is more suited for higher-dimensional inputs, and rounding steps which transform axis-parallel boxes, on which the discrepancy is to be tested, into \emph{critical test boxes}. These critical test boxes provably yield higher discrepancy values, and contain the box that exhibits the maximum value of the local discrepancy. We provide comprehensive experiments to test the new algorithm. Our randomized algorithm computes the exact discrepancy frequently in all cases where this can be checked (i.e., where the exact discrepancy of the point set can be computed in feasible time). Most importantly, in higher dimension the new method behaves clearly better than all previously known methods.

References in corpus (1)

• Hardness of discrepancy computation and epsilon-net verification in high dimension

Cited by in corpus (13)

• Calculation of Discrepancy Measures and Applications
• Constructing Low Star Discrepancy Point Sets with Genetic Algorithms
• Density Estimation via Discrepancy Based Adaptive Sequential Partition
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms
• Overcoming the numerical sign problem in the Wigner dynamics via adaptive particle annihilation
• SPADE: Sequential-clustering Particle Annihilation via Discrepancy Estimation
• Density Estimation via Discrepancy
• An ODE approach to multiple choice polynomial programming
• The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension
• An efficient stochastic particle method for high-dimensional nonlinear PDEs
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
• A Nonlocal Functional Promoting Low-Discrepancy Point Sets
• Computable error bounds for quasi-Monte Carlo using points with non-negative local discrepancy