Approximation Algorithms for the Partition Vertex Cover Problem

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.