2.00 pm, Seminar Hall
QPTAS for Set Cover in geometric settings
Rajiv Raman
IIIT, Delhi.
28-11-14

---

Abstract

In the classic set cover problem, we are given a ground set and a collection of subsets (possibly with weights). The goal is to find a minimum (weight) sub-collection that covers all points of the ground set.

The problem in abstract setting is well understood. There are several algorithms that achieve an O(log n)-approximation, while it has been shown that one can not do better unless P=NP.

We consider the geometric setting, where the ground set is a set of points and the sets are defined by geometric shapes. For many geometric problems, we suspect we can obtain better approximation algorithms than in the abstract setting. However, there are large gaps between the best approximation algorithms and hardness results.

We show that in several geometric settings, we can obtain a QPTAS, i.e., a $(1+\epsilon)$-approximation that runs in $2^{O(poly \log n}}$. This is joint work with Nabil Mustafa and Saurabh Ray.