Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
From MaRDI portal
Publication:1023397
DOI10.1016/j.jco.2008.10.001zbMath1167.65015MaRDI QIDQ1023397
Anand Srivastav, Michael Gnewuch, Carola Winzen
Publication date: 11 June 2009
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2008.10.001
65D18: Numerical aspects of computer graphics, image analysis, and computational geometry
65Y20: Complexity and performance of numerical algorithms
Related Items
Discrepancy Theory and Quasi-Monte Carlo Integration, Calculation of Discrepancy Measures and Applications, Entropy, Randomization, Derandomization, and Discrepancy, An Intermediate Bound on the Star Discrepancy, Probabilistic discrepancy bound for Monte Carlo point sets, A Metropolis random walk algorithm to estimate a lower bound of the star discrepancy, On the expected \(\mathcal{L}_2\)-discrepancy of jittered sampling, Isovolumetric adaptations to space-filling design of experiments, Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension, Consistency of Markov chain quasi-Monte Carlo on continuous state spaces, Algorithmic construction of low-discrepancy point sets via dependent randomized rounding, Secure pseudorandom bit generators and point sets with low star-discrepancy, A random walk algorithm to estimate a lower bound of the star discrepancy, Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions, New bounds on the minimal dispersion, Deterministic constructions of high-dimensional sets with small dispersion, A table of short-period Tausworthe generators for Markov chain quasi-Monte Carlo, An enumerative formula for the spherical cap discrepancy, Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples, Tractability results for the weighted star-discrepancy, A nonlocal functional promoting low-discrepancy point sets, Uniform point sets and the collision test, Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series, Monte Carlo and quasi-Monte Carlo methods for Dempster's rule of combination, Construction Schemes for Weighted Lattice Rules, The Inverse of the Star-Discrepancy Problem and the Generation of Pseudo-Random Numbers, A genetic algorithm approach to estimate lower bounds of the star discrepancy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on E. Thiémard's algorithm to compute bounds for the star discrepancy
- Sequences, discrepancies and applications
- Funktionen von beschränkter Variation in der Theorie der Gleichverteilung
- Relaxed verification for continuous problems
- An algorithm to compute bounds for the star discrepancy
- Optimal volume subintervals with \(k\) points and star discrepancy via integer programming
- Computing bounds for the star discrepancy
- Algorithmics for hard problems.
- Discrepancy and convex programming
- Computing discrepancies of Smolyak quadrature rules
- Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- Component-by-component construction of low-discrepancy point sets of small size
- 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
- Efficient algorithms for computing the $L_2$-discrepancy
- On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
- Some applications of multidimensional integration by parts
- The NP-completeness column: An ongoing guide
- Geometric discrepancy. An illustrated guide
