Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension (Q413466): Difference between revisions
From MaRDI portal
Changed an Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 03:42, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension |
scientific article |
Statements
Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension (English)
0 references
7 May 2012
0 references
The star discrepancy (or geometric discrepancy with respect to corners) of a set \(P\) of \(n\) points in the \(d\)-dimensional unit cube \([0,1]^d\) is the supremum, taken over all axis-parallel rectangles \(R = [0,x] \subseteq [0,1]^d\) (``corners''), absolute deviation of the number of points in \(R\) from the expected value \(n \lambda(R)\), where \(\lambda\) denotes the \(d\)-dimensional Lebesgue measure. It is well known that the star discrepancy of an \(n\)-point set can be computed in time \(n^{O(d)}\). Also, the decision problem if the star discrepancy exceeds a given value, is NP-hard if \(d\) is part of the input. This work presents a stronger lower bound by showing that the decision problem is even W[1]-hard with respect to \(d\). Consequently, algorithms with runtime bounded by \(f(d) n^{O(1)}\) do not exist unless FPT = W[1]. Analogous results are shown for the decision versions of a number of related problems: Computing the largest empty corner, the largest empty axis parallel rectangle, the red-blue discrepancy with respect to axis-parallel rectangles and several others. The first of these is even hard even to approximate within a factor of \(2^n\). Also, the problem of deciding whether a subset \(S\) of \(P\) is an \(\varepsilon\)-net with respect to half-spaces, is co-NP-hard and co-W[1]-hard.
0 references
discrepancy
0 references
epsilon-nets
0 references
geometric dimension
0 references
parameterized complexity
0 references
inapproximability
0 references