Finding optimal volume subintervals with k points and calculating the star discrepancy are NP-hard problems
From MaRDI portal
(Redirected from Publication:1023397)
Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
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
Cites work
- scientific article; zbMATH DE number 53679 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 735224 (Why is no real title available?)
- scientific article; zbMATH DE number 1528185 (Why is no real title available?)
- scientific article; zbMATH DE number 863495 (Why is no real title available?)
- scientific article; zbMATH DE number 3393648 (Why is no real title available?)
- A note on E. Thiémard's algorithm to compute bounds for the star discrepancy
- Algorithmics for hard problems.
- An algorithm to compute bounds for the star discrepancy
- Application of Threshold-Accepting to the Evaluation of the Discrepancy of a Set of Points
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
- Component-by-component construction of low-discrepancy point sets of small size
- Computing bounds for the star discrepancy
- Computing discrepancies of Smolyak quadrature rules
- Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding
- Discrepancy and convex programming
- Efficient algorithms for computing the $L_2$-discrepancy
- Funktionen von beschränkter Variation in der Theorie der Gleichverteilung
- Geometric discrepancy. An illustrated guide
- On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
- Optimal volume subintervals with \(k\) points and star discrepancy via integer programming
- Relaxed verification for continuous problems
- Sequences, discrepancies and applications
- Some applications of multidimensional integration by parts
- The NP-completeness column: An ongoing guide
- The inverse of the star-discrepancy depends linearly on the dimension
- When are integration and discrepancy tractable?
Cited in
(31)- On the expected \(\mathcal{L}_2\)-discrepancy of jittered sampling
- 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
- Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
- Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions
- Construction schemes for weighted lattice rules
- 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
- 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
- On the discrepancy of low-dimensional probability measures
- 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
- Uniform point sets and the collision test
- A new randomized algorithm to approximate the star discrepancy based on threshold accepting
- 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
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)
