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.001zbMATH Open1167.65015OpenAlexW2162820178MaRDI QIDQ1023397FDOQ1023397
Authors: Michael Gnewuch, Anand Srivastav, 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
Recommendations
- Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
- Optimal volume subintervals with \(k\) points and star discrepancy via integer programming
- Some open problems concerning the star-discrepancy
- Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions
- A new randomized algorithm to approximate the star discrepancy based on threshold accepting
Complexity and performance of numerical algorithms (65Y20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sequences, discrepancies and applications
- Title not available (Why is that?)
- Geometric discrepancy. An illustrated guide
- Title not available (Why is that?)
- Funktionen von beschränkter Variation in der Theorie der Gleichverteilung
- Application of Threshold-Accepting to the Evaluation of the Discrepancy of a Set of Points
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some applications of multidimensional integration by parts
- An algorithm to compute bounds for the star discrepancy
- Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
- Efficient algorithms for computing the $L_2$-discrepancy
- Computing bounds for the star discrepancy
- Computing discrepancies of Smolyak quadrature rules
- The inverse of the star-discrepancy depends linearly on the dimension
- The NP-completeness column: An ongoing guide
- When are integration and discrepancy tractable?
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- A note on E. Thiémard's algorithm to compute bounds for the star discrepancy
- On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
- Relaxed verification for continuous problems
- 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
- Optimal volume subintervals with \(k\) points and star discrepancy via integer programming
- Algorithmics for hard problems.
- Discrepancy and convex programming
Cited In (31)
- Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
- A table of short-period Tausworthe generators for Markov chain quasi-Monte Carlo
- Consistency of Markov chain quasi-Monte Carlo on continuous state spaces
- A genetic algorithm approach to estimate lower bounds of the star discrepancy
- An enumerative formula for the spherical cap discrepancy
- Construction schemes for weighted lattice rules
- Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions
- Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
- Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
- Isovolumetric adaptations to space-filling design of experiments
- Secure pseudorandom bit generators and point sets with low star-discrepancy
- Deterministic constructions of high-dimensional sets with small dispersion
- New bounds on the minimal dispersion
- Probabilistic discrepancy bound for Monte Carlo point sets
- An intermediate bound on the star discrepancy
- On the discrepancy of low-dimensional probability measures
- Optimal volume subintervals with \(k\) points and star discrepancy via integer programming
- A random walk algorithm to estimate a lower bound of the star discrepancy
- Monte Carlo and quasi-Monte Carlo methods for Dempster's rule of combination
- Calculation of discrepancy measures and applications
- A Metropolis random walk algorithm to estimate a lower bound of the star discrepancy
- Discrepancy theory and quasi-Monte Carlo integration
- A new randomized algorithm to approximate the star discrepancy based on threshold accepting
- Uniform point sets and the collision test
- The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
- Entropy, Randomization, Derandomization, and Discrepancy
- Heuristic approaches to obtain low-discrepancy point sets via subset selection
- Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series
- A nonlocal functional promoting low-discrepancy point sets
- Tractability results for the weighted star-discrepancy
- On the expected \(\mathcal{L}_2\)-discrepancy of jittered sampling
This page was built for publication: Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1023397)
