BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1232
DTSTAMP:20230914T125955Z
SUMMARY:A game theoretic proof of RANKING algorithm
DESCRIPTION:Speaker: Soumyajit Pyne\n\nAbstract: \nOnline Bipartitie Matchi
 ng was first introduced by Karp\, Vazirani and Vazirani (STOC’90). In th
 eir seminal paper they had inroduced the RANKING algorithm which admits a 
 tight competitive ratio of 1-1/e. Since then multiple proofs of RANKING ha
 ve been published. In this talk\, we shall look at a simple Game Theoretic
  approach to proving the competitive ratio of RANKING\, avoiding linear pr
 ogramming arguments. The proof is based on the paper by Eden\, Feldman\, F
 iat and Segal (https://arxiv.org/abs/1804.06637).\n
URL:https://www.tcs.tifr.res.in/web/events/1232
DTSTART;TZID=Asia/Kolkata:20220812T160000
DTEND;TZID=Asia/Kolkata:20220812T170000
LOCATION:A201
END:VEVENT
END:VCALENDAR