School of Technology and Computer Science Seminars
Approximation Algorithms for the Partition Vertex Cover Problem
by Mr. Pritam Bhattacharya (Schoolof Technology and Computer Science, TIFR)
Friday, March 1, 2013
from
to
(Asia/Kolkata)
at Colaba Campus ( A-212 (STCS Seminar Room) )
at Colaba Campus ( A-212 (STCS Seminar Room) )
Description |
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 P1,...,Pr of the edge set E, and a parameter ki for each partition Pi. The goal is to find a minimum cost set of vertices which cover at least ki edges from the partition Pi. 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. |