Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
From MaRDI portal
Publication:708312
DOI10.1016/j.jco.2010.03.004zbMath1204.65006MaRDI 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
numerical experiments; derandomization; randomized rounding; star discrepancy; deterministic algorithm; low-discrepancy points
65G50: Roundoff error
65C10: Random number generation in numerical analysis
11K38: Irregularities of distribution, discrepancy
Related Items
A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy, Calculation of Discrepancy Measures and Applications, Entropy, Randomization, Derandomization, and Discrepancy, Probabilistic discrepancy bound for Monte Carlo point sets, Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension, Secure pseudorandom bit generators and point sets with low star-discrepancy, Deterministic constructions of high-dimensional sets with small dispersion, Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples, Tractability results for the weighted star-discrepancy, Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series, Infinite-dimensional integration on weighted Hilbert spaces, The Inverse of the Star-Discrepancy Problem and the Generation of Pseudo-Random Numbers, Some Results on the Complexity of Numerical Integration
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
