In the Set Cover problem, the input is a set system $(X,\mathcal{S})$, such that $\cup_{S\in\mathcal{S}} S=X$. The objective is to select a smallest cardinality set $\mathcal{S}'\subseteq{S}$ such that the sets in $\mathcal{S}'$ cover $X$, i.e., for each $x\in X$, there is an $S\in\mathcal{S}'$ s.t. $x\in S$. In the Set Packing problem, the input is the same and the goal is to select a largest cardinality set $\mathcal{S}'\subseteq\mathcal{S}$ such that for each element $x\in X$, there is at most one set in $\mathcal{S}'$ containing it. That is, $|\{S\in\mathcal{S}': x\in S\}|\le 1$.
The Set Cover and Set Packing problems are classic examples of packing and covering problems. In a geometric set system, the sets $X$ and $\mathcal{S}$ are geometric objects. We consider the setting where $X$ is a set of points in the plane and $\mathcal{S}$ is a set of regions in the plane, where the set corresponding to a region contains all points in its interior. Our goal is to build techniques that exploit the underlying geometry to obtain better algorithms than in the general setting.
We present some general conditions, namely \emph{non-piercing} under which algorithms with good approximation factors can be obtained for the problems above, and then describe some recent results where we can obtain improved approximations even if we allow \emph{piercings}.
The talk is based on joint work with Saurabh Ray, Aritra Banik, Siddhartha Sarkar and Jatin Yadav, Karamjeet Singh and Suryendu Dalal.
Bio: Rajiv Raman is an associate professor at IIIT-Delhi. He obtained his PhD from the University of Iowa, and then spent some time as a postdoc at the Max-Planck Institute in Saarbrucken and at the Centre for Discrete Mathematics and Applications, University of Warwick.
