Bringmann, Karl ;
KisfaludiBak, Sándor ;
Pilipczuk, Michal ;
van Leeuwen, Erik Jan
On Geometric Set Cover for Orthants
Abstract
We study SET COVER for orthants: Given a set of points in a ddimensional 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 multiobjective 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 sizek 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 halfspaces in dimension 3. In particular, we show that given a set of points U in R^3, a set of halfspaces D in R^3, and an integer k, one can decide whether U can be covered by the union of at most k halfspaces 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.05approximation 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 KisfaludiBak 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:126:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11147},
URN = {urn:nbn:de:0030drops111476},
doi = {10.4230/LIPIcs.ESA.2019.26},
annote = {Keywords: Set Cover, parameterized complexity, algorithms, Exponential Time Hypothesis}
}
06.09.2019
Keywords: 

Set Cover, parameterized complexity, algorithms, Exponential Time Hypothesis 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 