Let B be a set of n axis-parallel boxes in d-dimensions such that each box has a corner at the origin and the other corner in the positive quadrant, and let k be a positive integer. We study the problem of selecting k boxes in B that maximize the volume of the union of the selected boxes. The research is motivated by applications in skyline queries for databases and in multicriteria optimization, where the problem is known as the hypervolume subset selection problem. It is known that the problem can be solved in polynomial time in the plane, while the best known algorithms in any dimension d>2 enumerate all size-k subsets. We show that: * The problem is NP-hard already in 3 dimensions. * In 3 dimensions, we break the enumeration of all size-k subsets, by providing an n^O(sqrt(k)) algorithm. * For any constant dimension d, we give an efficient polynomial-time approximation scheme.
@cite_0: 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.
@cite_5: Klee’s Measure Problem (KMP) asks for the volume of the union of n axis-aligned boxes in ℝ d . Omitting logarithmic factors, the best algorithm has runtime ( O ^*(n^ d 2 ) ) [Overmars,Yap’91]. There are faster algorithms known for several special cases: Cube-KMP (where all boxes are cubes), Unitcube-KMP (where all boxes are cubes of equal side length), Hypervolume (where all boxes share a vertex), and k -Grounded (where the projection onto the first k dimensions is a Hypervolume instance).
@cite_27: The hypervolume indicator is an increasingly popular set measure to compare the quality of two Pareto sets. The basic ingredient of most hypervolume indicator based optimization algorithms is the calculation of the hypervolume contribution of single solutions regarding a Pareto set. We show that exact calculation of the hypervolume contribution is #P-hard while its approximation is NP-hard. The same holds for the calculation of the minimal contribution. We also prove that it is NP-hard to decide whether a solution has the least hypervolume contribution. Even deciding whether the contribution of a solution is at most (1+@e) times the minimal contribution is NP-hard. This implies that it is neither possible to efficiently find the least contributing solution (unless P=NP) nor to approximate it (unless NP=BPP). Nevertheless, in the second part of the paper we present a fast approximation algorithm for this problem. We prove that for arbitrarily given @e,@d>0 it calculates a solution with contribution at most (1+@e) times the minimal contribution with probability at least (1-@d). Though it cannot run in polynomial time for all instances, it performs extremely fast on various benchmark datasets. The algorithm solves very large problem instances which are intractable for exact algorithms (e.g., 10,000 solutions in 100 dimensions) within a few seconds.
@cite_2: Given n axis-parallel boxes in a fixed dimension d>=3, how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee's measure problem, can be solved in time O(n^d^ ^2logn) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time n^d^ ^22^O^(^l^o^g^^^*^n^), where log^* denotes the iterated logarithm. For the related problem of computing the depth in an arrangement of n boxes, we further improve the time bound to near O(n^d^ ^2 log^d^ ^2^-^1n), ignoring loglogn factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple.
Chan @cite_2 gave a reduction from @math -Clique to Klee's measure problem in @math dimensions. This proves NP-hardness of Klee's measure problem when @math is part of the input (and thus @math can be as large as @math ). Moreover, since @math -Clique has no @math -time algorithm under the Exponential Time Hypothesis @cite_0 , Klee's measure problem has no @math -time algorithm under the same assumption. The same hardness results also hold for Klee's measure problem on anchored boxes, by a reduction in @cite_5 (NP-hardness was first proven in @cite_27 ).