Bounds and constructions for the star-discrepancy via -covers

DOI10.1016/J.JCO.2005.05.002MaRDI QIDQ2576276zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Michael Gnewuch, 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 numberderandomizationHoeffding's inequalitylow-discrepancy point setsstar-discrepancy

Mathematics Subject Classification ID

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

Recommendations

• Entropy, Randomization, Derandomization, and Discrepancy
• The inverse of the star-discrepancy depends linearly on the dimension
• Computing bounds for the star discrepancy
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• Probabilistic discrepancy bound for Monte Carlo point sets

Cites work

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

Cited in

(41)

• Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
• An algorithm to compute bounds for the star discrepancy
• Computing bounds for the star discrepancy
• Tractability properties of the weighted star discrepancy of the Halton sequence
• Secure pseudorandom bit generators and point sets with low star-discrepancy
• Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
• On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence
• A nonlocal functional promoting low-discrepancy point sets
• Theory of generalized discrepancies on a ball of arbitrary finite dimensions and algorithms for finding low-discrepancy point sets
• Minimizing the \(L_{2}\) and \(L_{\infty}\) star discrepancies of a single point in the unit hypercube
• A note on the existence of sequences with small star discrepancy
• Tractability properties of the weighted star discrepancy
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Bounds for the average \(L^p\)-extreme and the \(L^\infty\)-extreme discrepancy
• A new randomized algorithm to approximate the star discrepancy based on threshold accepting
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
• Discrepancy estimates for acceptance-rejection samplers using stratified inputs
• A best possible upper bound on the star discrepancy of (t, m, 2)-nets
• The weighted star discrepancy of Korobov’s p-sets
• Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding
• Component-by-component construction of low-discrepancy point sets of small size
• The inverse of the star-discrepancy depends linearly on the dimension
• Irregularities of distributions and extremal sets in combinatorial complexity theory
• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• A sharp discrepancy bound for jittered sampling
• Metrical star discrepancy bounds for lacunary subsequences of digital Kronecker-sequences and polynomial tractability
• Discrepancy theory and quasi-Monte Carlo integration
• Calculation of discrepancy measures and applications
• Entropy, Randomization, Derandomization, and Discrepancy
• Probabilistic discrepancy bound for Monte Carlo point sets
• Low-discrepancy point sets for non-uniform measures
• Functions of bounded variation, signed measures, and a general Koksma–Hlawka inequality
• A note on E. Thiémard's algorithm to compute bounds for the star discrepancy
• A Metropolis random walk algorithm to estimate a lower bound of the star discrepancy
• Covering numbers, dyadic chaining and discrepancy
• Upper bound estimation of star discrepancy based on Hilbert space filling curve stratified sampling and its applications
• Hammersley point sets and inverse of star-discrepancy
• Constructing optimal star discrepancy sets
• Probabilistic weighted star discrepancy bound based on the general equal measure partition
• Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2576276)