 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.26
URN: urn:nbn:de:0030-drops-111476
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11147/
 Go to the corresponding LIPIcs Volume Portal

### On Geometric Set Cover for Orthants

 pdf-format:

### Abstract

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] x ... x (-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 >= 3, when k is considered a parameter: - For d=3, we give an algorithm with runtime n^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 >=slant 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 R^3, a set of half-spaces D in R^3, and an integer k, one can decide whether U can be covered by the union of at most k half-spaces from D in time |D|^O(sqrt{k})* |U|^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)* n^o(k) for any computable f, where k is the optimum.

### BibTeX - Entry

```@InProceedings{bringmann_et_al:LIPIcs:2019:11147,
author =	{Karl Bringmann and S{\'a}ndor Kisfaludi-Bak and Michal Pilipczuk and Erik Jan van Leeuwen},
title =	{{On Geometric Set Cover for Orthants}},
booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
pages =	{26:1--26:18},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-124-5},
ISSN =	{1868-8969},
year =	{2019},
volume =	{144},
editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 