Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
From MaRDI portal
Publication:413466
DOI10.1016/j.jco.2011.09.001zbMath1273.11116OpenAlexW1508410079MaRDI QIDQ413466
Magnus Wahlström, Christian Knauer, Daniel Werner, Panos Giannopoulos
Publication date: 7 May 2012
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2011.09.001
Complexity and performance of numerical algorithms (65Y20) Irregularities of distribution, discrepancy (11K38)
Related Items
Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions ⋮ Entropy, Randomization, Derandomization, and Discrepancy ⋮ Faster algorithms for largest empty rectangles and boxes ⋮ 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 ⋮ On the number of maximum empty boxes amidst \(n\) points ⋮ Calculation of Discrepancy Measures and Applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the efficiency of polynomial time approximation schemes
- Sequences, discrepancies and applications
- Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
- Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
- \(\epsilon\)-nets and simplex range queries
- An algorithm to compute bounds for the star discrepancy
- The maximum box problem and its application to data analysis
- On the largest empty axis-parallel box amidst \(n\) points
- Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
- Parametrized complexity theory.
- Tight lower bounds for certain parameterized NP-hard problems
- Geometric clustering
- The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
- On Approximating the Depth and Related Problems
- Tight lower bounds for the size of epsilon-nets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Geometric discrepancy. An illustrated guide
