2026-07-24T00:34:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11147 2024-03-06T10:47:33Z ddc:004 open_access

On Geometric Set Cover for Orthants Bringmann, Karl Kisfaludi-Bak, Sándor Pilipczuk, Michał van Leeuwen, Erik Jan Set Cover parameterized complexity algorithms Exponential Time Hypothesis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karl Bringmann and Sándor Kisfaludi-Bak and Michał Pilipczuk and Erik Jan van Leeuwen 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.26 urn:nbn:de:0030-drops-111476 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.26 eng https://creativecommons.org/licenses/by/3.0/legalcode