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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11147/
Bringmann, Karl ;
Kisfaludi-Bak, 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 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},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11147},
URN = {urn:nbn:de:0030-drops-111476},
doi = {10.4230/LIPIcs.ESA.2019.26},
annote = {Keywords: Set Cover, parameterized complexity, algorithms, Exponential Time Hypothesis}
}
|
Keywords: |
|
Set Cover, parameterized complexity, algorithms, Exponential Time Hypothesis |
|
Collection: |
|
27th Annual European Symposium on Algorithms (ESA 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.09.2019 |
