Speaker: |
Rajiv Raman (Indraprastha Institute of Information Technology Okhla Industrial Estate Phase III (Near Govind Puri Metro Station) New Delhi 110020) |

Organiser: |
Umang Bhaskar |

Date: |
Tuesday, 8 Dec 2015, 16:00 to 17:00 |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

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.