BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/344
DTSTAMP:20230914T125920Z
SUMMARY:Approximation Algorithms for the Partition Vertex Cover Problem
DESCRIPTION:Speaker: Pritam Bhattacharya\n\nAbstract: \nLet us consider a n
 atural generalization of the Partial Vertex Cover problem. Here\, an insta
 nce 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 se
 t 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 mat
 ching upper and lower bounds on the approximability of this problem. The a
 pproximation algorithm that will be shown is based on a novel LP relaxatio
 n for this problem\, which is obtained by adding knapsack cover inequaliti
 es to a natural LP relaxation of the problem. Further\, it will be shown t
 hat this LP has an integrality gap of O(log r)\, where r is the number of 
 sets in the partition of the edge set.\n
URL:https://www.tcs.tifr.res.in/web/events/344
DTSTART;TZID=Asia/Kolkata:20130301T143000
DTEND;TZID=Asia/Kolkata:20130301T160000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR