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.
