Tata Institute of Fundamental Research
Approximation Algorithms for Geometric Covering and Packing Problems
STCS Colloquium
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)
Abstract:
Abstract: 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.
| 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)
Abstract:
Abstract: 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.
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.