## 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 (−∞, p_{1}] × . . . × (−∞, 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(√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) · n^{o(k)} for any computable f, where k is the optimum.

Original language | English |
---|---|

Title of host publication | 27th Annual European Symposium on Algorithms, ESA 2019 |

Editors | Michael A. Bender, Ola Svensson, Grzegorz Herman |

Place of Publication | Dagstuhl |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Number of pages | 18 |

ISBN (Electronic) | 9783959771245 |

DOIs | |

Publication status | Published - 1 Sep 2019 |

Event | 27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany Duration: 9 Sep 2019 → 11 Sep 2019 |

### Publication series

Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|

Volume | 144 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 27th Annual European Symposium on Algorithms, ESA 2019 |
---|---|

Country | Germany |

City | Munich/Garching |

Period | 9/09/19 → 11/09/19 |

## Keywords

- Algorithms
- Exponential time hypothesis
- Parameterized complexity
- Set cover
- Set Cover
- algorithms
- Exponential Time Hypothesis
- parameterized complexity