| Description |
In the classic set cover problem we are given a finite ground set $X$ of elements and a collection of subsets of $X$ whose union covers $X$. The problem is to find a sub-collection of smallest cardinality from the given collection that still forms a cover of $X$. In the classic packing problem, we want the largest cardinality sub-collection that are pairwise disjoint. These classic problems are well reasonably well understood in the abstract setting.
In this talk, we consider these problems in the geometric setting. Here, the elements of $X$ are points in the plane, and the subsets of $X$ are defined by geometric regions. These problems are not as well understood in the geometric setting. For example, there are gaps between the unweighted setting described above, and the weighted setting in which the sets have weights and we want to find the minimum (or maximum) weight sub-collection that forms a cover (or forms a packing).
We present approximation algorithms for the covering problem where the sets are non-piercing, i.e., for any two regions simply connected $A$ and $B$, the regions $AB$ and $BA$ are connected. We extend these results to a related covering problem, namely the dominating set problem as well as a generalization of the packing problem where the points (or sets) have capacities that are bounded by a constant. The results in this talk were obtained jointly with Aniket Basu, Sathish Govindarajan, Nabil Mustafa and Saurabh Ray.
|