Bounds and constructions for the star-discrepancy via \(\delta\)-covers

DOI10.1016/j.jco.2005.05.002zbMath1115.11046OpenAlexW2138926885MaRDI QIDQ2576276

Michael Gnewuch, Benjamin Doerr, Anand Srivastav

Publication date: 27 December 2005

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

Full work available at URL: https://doi.org/10.1016/j.jco.2005.05.002

zbMATH Keywords

covering numberlow-discrepancy point setsstar-discrepancyderandomizationHoeffding's inequality

Mathematics Subject Classification ID

Numerical integration (65D30) Irregularities of distribution, discrepancy (11K38)

Related Items (19)

The weighted star discrepancy of Korobov’s $p$-sets ⋮ A sharp discrepancy bound for jittered sampling ⋮ Entropy, Randomization, Derandomization, and Discrepancy ⋮ The Inverse of the Star-Discrepancy Problem and the Generation of Pseudo-Random Numbers ⋮ Discrepancy Estimates For Acceptance-Rejection Samplers Using Stratified Inputs ⋮ Component-by-component construction of low-discrepancy point sets of small size ⋮ Tractability properties of the weighted star discrepancy of the Halton sequence ⋮ Covering numbers, dyadic chaining and discrepancy ⋮ A note on the existence of sequences with small star discrepancy ⋮ Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples ⋮ Tractability properties of the weighted star discrepancy ⋮ Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy ⋮ Algorithmic construction of low-discrepancy point sets via dependent randomized rounding ⋮ On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence ⋮ A nonlocal functional promoting low-discrepancy point sets ⋮ A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy ⋮ Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems ⋮ Discrepancy Theory and Quasi-Monte Carlo Integration ⋮ Calculation of Discrepancy Measures and Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sequences, discrepancies and applications
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• On the tractability of multivariate integration and approximation by neural networks
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• Some open problems concerning the star-discrepancy
• Improved algorithms via approximations of probability distributions
• Bounds for the average \(L^p\)-extreme and the \(L^\infty\)-extreme discrepancy
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• The inverse of the star-discrepancy depends linearly on the dimension
• On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
• Convergence of stochastic processes
• Geometric discrepancy. An illustrated guide

This page was built for publication: Bounds and constructions for the star-discrepancy via \(\delta\)-covers