On geometric set cover for orthants

Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, Erik Jan van Leeuwen

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Downloads (Pure)


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 (−∞, p1] × . . . × (−∞, pd], 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 nO(√k), thus avoiding exhaustive enumeration. ⁃ For d = 3, we prove a tight lower bound of nΩ(√k) (assuming ETH). ⁃ For d ≥ 4, we prove a tight lower bound of nΩ(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 ℝ3, a set of half-spaces D in ℝ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(√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) · no(k) for any computable f, where k is the optimum.

Originele taal-2Engels
Titel27th Annual European Symposium on Algorithms, ESA 2019
RedacteurenMichael A. Bender, Ola Svensson, Grzegorz Herman
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's18
ISBN van elektronische versie9783959771245
StatusGepubliceerd - 1 sep 2019
Evenement27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Duitsland
Duur: 9 sep 201911 sep 2019

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
ISSN van geprinte versie1868-8969


Congres27th Annual European Symposium on Algorithms, ESA 2019

Vingerafdruk Duik in de onderzoeksthema's van 'On geometric set cover for orthants'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Bringmann, K., Kisfaludi-Bak, S., Pilipczuk, M., & van Leeuwen, E. J. (2019). On geometric set cover for orthants. In M. A. Bender, O. Svensson, & G. Herman (editors), 27th Annual European Symposium on Algorithms, ESA 2019 [26] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 144). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2019.26