Algorithmic construction of low-discrepancy point sets via dependent randomized rounding

DOI10.1016/j.jco.2010.03.004zbMath1204.65006OpenAlexW2110972762MaRDI QIDQ708312

Michael Gnewuch, Benjamin Doerr, Magnus Wahlström

Publication date: 11 October 2010

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

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

zbMATH Keywords

numerical experimentsderandomizationrandomized roundingstar discrepancydeterministic algorithmlow-discrepancy points

Mathematics Subject Classification ID

Roundoff error (65G50) Random number generation in numerical analysis (65C10) Irregularities of distribution, discrepancy (11K38)

Related Items (13)

Deterministic constructions of high-dimensional sets with small dispersion ⋮ Entropy, Randomization, Derandomization, and Discrepancy ⋮ The Inverse of the Star-Discrepancy Problem and the Generation of Pseudo-Random Numbers ⋮ Some Results on the Complexity of Numerical Integration ⋮ Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension ⋮ Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series ⋮ Probabilistic discrepancy bound for Monte Carlo point sets ⋮ Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples ⋮ Tractability results for the weighted star-discrepancy ⋮ Secure pseudorandom bit generators and point sets with low star-discrepancy ⋮ A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy ⋮ Infinite-dimensional integration on weighted Hilbert spaces ⋮ 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
• Construction of minimal bracketing covers for rectangles
• Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
• A method for exact calculation of the stardiscrepancy of plane sets applied to the sequences of Hammersley
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• A method for exact calculation of the discrepancy of low-dimensional finite point sets. I
• An algorithm to compute bounds for the star discrepancy
• Low-discrepancy sequences and global function fields with many rational places
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• Implementation of a Component-By-Component Algorithm to Generate Small Low-Discrepancy Samples
• Component-by-component construction of low-discrepancy point sets of small size
• Dependent rounding and its applications to approximation algorithms
• MONTE CARLO METHODS FOR SOLVING MULTIVARIABLE PROBLEMS
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Application of Threshold-Accepting to the Evaluation of the Discrepancy of a Set of Points
• The inverse of the star-discrepancy depends linearly on the dimension
• On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
• Randomized Rounding in the Presence of a Cardinality Constraint
• Generating Randomized Roundings with Cardinality Constraints and Derandomizations

This page was built for publication: Algorithmic construction of low-discrepancy point sets via dependent randomized rounding