On Geometric Set Cover for Orthants

Prelegent(ci)

Erik Jan van Leeuwen

Afiliacja

Utrecht University

Termin

12 grudnia 2019 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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 >= 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. We also study approximation for Set Cover for orthants. This talk is based on joint work with Karl Bringmann, Sándor Kisfaludi-Bak, and Michał Pilipczuk that appeared in ESA 2019.

---