Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. There are two notions of discrepancy, namely continuous discrepancy and combinatorial discrepancy. Depending on the ranges, several possible variants arise, for example star discrepancy, box discrepancy, and discrepancy of half-spaces. In this paper, we investigate the hardness of these problems with respect to the dimension d of the underlying space. All these problems are solvable in time n^O(d) , but such a time dependency quickly becomes intractable for high-dimensional data. Thus it is interesting to ask whether the dependency on d can be moderated. We answer this question negatively by proving that the canonical decision problems are W[1]-hard with respect to the dimension. This is done via a parameterized reduction from the Clique problem. As the parameter stays linear in the input parameter, the results moreover imply that these problems require n^ (d) time, unless 3-Sat can be solved in 2^o(n) time. Further, we derive that testing whether a given set is an -net with respect to half-spaces takes n^ (d) time under the same assumption. As intermediate results, we discover the W[1]-hardness of other well known problems, such as determining the largest empty star inside the unit cube. For this, we show that it is even hard to approximate within a factor of 2^n .
When the dimension is part of the input, the problem was shown to be @math -hard by @cite_21 ; in the same paper an @math -time algorithm was given. @cite_8 gave an algorithm that runs in @math time, where @math is the number of feasible boxes that are not properly contained in any feasible box, and showed that @math can be @math in the worst case. @cite_17 gave an @math -approximation algorithm that runs in @math time.
@cite_21 @cite_17 @cite_8
2567804199 1554201860 1493107308 1987681136
An important question in theoretical computer science is to determine the best possible running time for solving a problem at hand. For geometric optimization problems, we often understand their complexity on a rough scale, but not very well on a finer scale. One such example is the two-dimensional knapsack problem for squares. There is a polynomial time (1 + ϵ)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1 ϵ, i.e., Ω(n221 ϵ). A double or triple exponential dependence on 1 ϵ is inherent in how this and several other algorithms for other geometric problems work. In this paper, we present an EPTAS for knapsack for squares, i.e., a (1+ϵ)-approximation algorithm with a running time of Oϵ(1)·nO(1). In particular, the exponent of n in the running time does not depend on ϵ at all! Since there can be no FPTAS for the problem (unless P = NP) this is the best kind of approximation scheme we can hope for. To achieve this improvement, we introduce two new key ideas: We present a fast method to guess the Ω(221 ϵ) relatively large squares of a suitable near-optimal packing instead of using brute-force enumeration. Secondly, we introduce an indirect guessing framework to define sizes of cells for the remaining squares. In the previous PTAS each of these steps needs a running time of Ω(n221 ϵ) and we improve both to Oϵ(1) · nO(1). We complete our result by giving an algorithm for two-dimensional knapsack for rectangles under (1 + ϵ)-resource augmentation. In this setting, we also improve the best known running time of Ω(n1 ϵ1 ϵ) to Oϵ(1) · nO(1) and compute even a solution with optimal profit, in contrast to the best previously known polynomial time algorithm for this setting that computes only an approximation. We believe that our new techniques have the potential to be useful for other settings as well. Given a matrix A e ℝ m ×n of rank r, and an integer k < r, the top k singular vectors provide the best rank-k approximation to A. When the columns of A have specific meaning, it is desirable to find (provably) "good" approximations to A k which use only a small number of columns in A. Proposed solutions to this problem have thus far focused on randomized algorithms. Our main result is a simple greedy deterministic algorithm with guarantees on the performance and the number of columns chosen. Specifically, our greedy algorithm chooses c columns from A with @math such that @math where C gr is the matrix composed of the c columns, @math is the pseudo-inverse of C gr ( @math is the best reconstruction of A from C gr), and ¼(A) is a measure of the coherence in the normalized columns of A. The running time of the algorithm is O(SVD(A k) + mnc) where SVD(A k) is the running time complexity of computing the first k singular vectors of A. To the best of our knowledge, this is the first deterministic algorithm with performance guarantees on the number of columns and a (1 + e) approximation ratio in Frobenius norm. The algorithm is quite simple and intuitive and is obtained by combining a generalization of the well known sparse approximation problem from information theory with an existence result on the possibility of sparse approximation. Tightening the analysis along either of these two dimensions would yield improved results. We give the first efficient (1−e)-approximation algorithm for the following problem: Given an axis-parallel d-dimensional box R in ℝ d containing n points, compute a maximum-volume empty axis-parallel d-dimensional box contained in R. The minimum of this quantity over all such point sets is of the order ( ( 1 n ) ). Our algorithm finds an empty axis-aligned box whose volume is at least (1−e) of the maximum in O((8ede −2) d ⋅nlog d n) time. No previous efficient exact or approximation algorithms were known for this problem for d≥4. As the problem has been recently shown to be NP-hard in arbitrarily high dimensions (i.e., when d is part of the input), the existence of an efficient exact algorithm is unlikely. We develop new techniques for deriving very strong computational lower bounds for a class of well-known NP-hard problems, including weighted satisfiability , dominating set , hitting set , set cover , clique , and independent set . For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k) no(k) for any function f, even if we restrict the parameter value k to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds are also derived for other problems in the above class. Our techniques can be extended to derive computational lower bounds on approximation algorithms for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1 e)no(1 e) for any function f unless an unlikely collapse occurs in parameterized complexity theory.