Summary: We study SET COVER for orthants: Given a set of points in a \(d\)-dimensional Euclidean space and a set of orthants of the form \((-\infty,p_1]\times\cdots\times(-\infty,p_d]\), select a minimum number of orthants so that every point is contained in at least one selected orthant. This problem draws its motivation from applications in multi-objective optimization problems. While for \(d=2\) the problem can be solved in polynomial time, for \(d>2\) no algorithm is known that avoids the enumeration of all size-\(k\) subsets of the input to test whether there is a set cover of size \(k\). Our contribution is a precise understanding of the complexity of this problem in any dimension \(d\ge 3\), when \(k\) is considered a parameter:

–

For \(d=3\), we give an algorithm with runtime \(n^{\mathcal{O}(\sqrt{k})}\), thus avoiding exhaustive enumeration.

–

For \(d=3\), we prove a tight lower bound of \(n^{\Omega(\sqrt{k})}\) (assuming ETH).

–

For \(d\ge 4\), we prove a tight lower bound of \(n^{\Omega(k)}\) (assuming ETH).

Here \(n\) is the size of the set of points plus the size of the set of orthants. The first statement comes as a corollary of a more general result: an algorithm for SET COVER for half-spaces in dimension 3. In particular, we show that given a set of points \(U\) in \(\mathbb{R}^3\), a set of half-spaces \(\mathcal{D}\) in \(\mathbb{R}^3\), and an integer \(k\), one can decide whether \(U\) can be covered by the union of at most \(k\) half-spaces from \(\mathcal{D}\) in time \(|\mathcal{D}|^{\mathcal{O}(\sqrt{k})}\cdot|U|^{\mathcal{O}(1)}\).
We also study approximation for SET COVER for orthants. While in dimension 3 a PTAS can be inferred from existing results, we show that in dimension 4 and larger, there is no 1.05-approximation algorithm with runtime \(f(k)\cdot n^{o(k)}\) for any computable \(f\), where \(k\) is the optimum.
For the entire collection see [Zbl 1423.68016].