Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems

DOI10.1016/j.jco.2008.10.001zbMath1167.65015OpenAlexW2162820178MaRDI 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

zbMATH Keywords

complexityNP-completenesscomputational geometrystar discrepancy

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Related Items (27)

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 ⋮ Construction Schemes for Weighted Lattice Rules ⋮ Entropy, Randomization, Derandomization, and Discrepancy ⋮ An Intermediate Bound on the Star Discrepancy ⋮ The Inverse of the Star-Discrepancy Problem and the Generation of Pseudo-Random Numbers ⋮ Monte Carlo and quasi-Monte Carlo methods for Dempster's rule of combination ⋮ A Metropolis random walk algorithm to estimate a lower bound of the star discrepancy ⋮ Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension ⋮ On the expected \(\mathcal{L}_2\)-discrepancy of jittered sampling ⋮ Isovolumetric adaptations to space-filling design of experiments ⋮ A table of short-period Tausworthe generators for Markov chain quasi-Monte Carlo ⋮ Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series ⋮ An enumerative formula for the spherical cap discrepancy ⋮ 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 ⋮ Consistency of Markov chain quasi-Monte Carlo on continuous state spaces ⋮ Algorithmic construction of low-discrepancy point sets via dependent randomized rounding ⋮ A nonlocal functional promoting low-discrepancy point sets ⋮ Secure pseudorandom bit generators and point sets with low star-discrepancy ⋮ A genetic algorithm approach to estimate lower bounds of the star discrepancy ⋮ A random walk algorithm to estimate a lower bound of the star discrepancy ⋮ Discrepancy Theory and Quasi-Monte Carlo Integration ⋮ Calculation of Discrepancy Measures and Applications ⋮ Uniform point sets and the collision test

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

This page was built for publication: Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems