Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
From MaRDI portal
Publication:413466
DOI10.1016/j.jco.2011.09.001zbMath1273.11116MaRDI 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
65Y20: Complexity and performance of numerical algorithms
11K38: Irregularities of distribution, discrepancy
Related Items
Calculation of Discrepancy Measures and Applications, Entropy, Randomization, Derandomization, and Discrepancy, Probabilistic discrepancy bound for Monte Carlo point sets, On the number of maximum empty boxes amidst \(n\) points
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
