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

DOI10.1016/J.JCO.2010.03.004zbMATH Open1204.65006OpenAlexW2110972762MaRDI QIDQ708312FDOQ708312

Authors: Benjamin Doerr, Michael Gnewuch, 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

Recommendations

• 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
• Deterministic constructions of high-dimensional sets with small dispersion
• Construction Algorithms for Digital Nets with Low Weighted Star Discrepancy
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers

zbMATH Keywords

numerical experimentsderandomizationdeterministic algorithmrandomized roundingstar discrepancylow-discrepancy points

Mathematics Subject Classification ID

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

Cites Work

• Low-discrepancy sequences and global function fields with many rational places
• Title not available (Why is that?)
• Sequences, discrepancies and applications
• Dependent rounding and its applications to approximation algorithms
• MONTE CARLO METHODS FOR SOLVING MULTIVARIABLE PROBLEMS
• Application of Threshold-Accepting to the Evaluation of the Discrepancy of a Set of Points
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• A method for exact calculation of the stardiscrepancy of plane sets applied to the sequences of Hammersley
• Title not available (Why is that?)
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• 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
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• The inverse of the star-discrepancy depends linearly on the dimension
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
• Construction of minimal bracketing covers for rectangles
• A method for exact calculation of the discrepancy of low-dimensional finite point sets. I
• Implementation of a component-by-component algorithm to generate small low-discrepancy samples
• 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
• Title not available (Why is that?)
• Randomized Rounding in the Presence of a Cardinality Constraint
• Generating Randomized Roundings with Cardinality Constraints and Derandomizations

Cited In (18)

• Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
• Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
• Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding
• Secure pseudorandom bit generators and point sets with low star-discrepancy
• Implementation of a component-by-component algorithm to generate small low-discrepancy samples
• Deterministic constructions of high-dimensional sets with small dispersion
• Title not available (Why is that?)
• Probabilistic discrepancy bound for Monte Carlo point sets
• Calculation of discrepancy measures and applications
• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• Infinite-dimensional integration on weighted Hilbert spaces
• A new randomized algorithm to approximate the star discrepancy based on threshold accepting
• Component-by-component construction of low-discrepancy point sets of small size
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
• Entropy, Randomization, Derandomization, and Discrepancy
• Some results on the complexity of numerical integration
• Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series
• Tractability results for the weighted star-discrepancy

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

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