Tata Institute of Fundamental Research
Approximation Algorithms for the Partition Vertex Cover Problem
Student Seminar
Speaker:
Pritam Bhattacharya
Organiser:
Tapan Shah
Date:
Friday, 1 Mar 2013, 14:30 to 16:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Let us consider a natural generalization of the Partial Vertex Cover problem. Here, an instance consists of a graph $G = (V,E)$, a cost function $c : V -> Z^{+}$, a partition $P_{1}, . . . , P_{r}$ of the edge set $E$, and a parameter $k_{i}$ for each partition $P_{i}$. The goal is to find a minimum cost set of vertices which cover at least $k_{i}$ edges from the partition $ P_{i}$. We call this the Partition-VC problem. In this talk, you will see matching upper and lower bounds on the approximability of this problem. The approximation algorithm that will be shown is based on a novel LP relaxation for this problem, which is obtained by adding knapsack cover inequalities to a natural LP relaxation of the problem. Further, it will be shown that this LP has an integrality gap of O(log r), where r is the number of sets in the partition of the edge set.
| Speaker: | Pritam Bhattacharya |
| Organiser: | Tapan Shah |
| Date: | Friday, 1 Mar 2013, 14:30 to 16:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Let us consider a natural generalization of the Partial Vertex Cover problem. Here, an instance consists of a graph $G = (V,E)$, a cost function $c : V -> Z^{+}$, a partition $P_{1}, . . . , P_{r}$ of the edge set $E$, and a parameter $k_{i}$ for each partition $P_{i}$. The goal is to find a minimum cost set of vertices which cover at least $k_{i}$ edges from the partition $ P_{i}$. We call this the Partition-VC problem. In this talk, you will see matching upper and lower bounds on the approximability of this problem. The approximation algorithm that will be shown is based on a novel LP relaxation for this problem, which is obtained by adding knapsack cover inequalities to a natural LP relaxation of the problem. Further, it will be shown that this LP has an integrality gap of O(log r), where r is the number of sets in the partition of the edge set.