BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/667
DTSTAMP:20230914T125933Z
SUMMARY:On Randomized Algorithms for Online Preemptive Matching
DESCRIPTION:Speaker: Sumedh Tirodkar (Indian Institute of Technology\nDepar
 tment of Computer Science\nand Engineering\nPowai\nMumbai 400076)\n\nAbstr
 act: \nThe second talk in this series will be given on Friday\, April 01\,
  2016 at 1600 hours in A-201.\n\nAbstract: In this series of two talks\, w
 e will investigate the power of randomized algorithms for the maximum card
 inality matching (MCM) and the maximum weight matching (MWM) problems in t
 he online preemptive model. In this model\, the edges of a graph are revea
 led one by one and the algorithm is required to always maintain a valid ma
 tching. On seeing an edge\, the algorithm has to either accept or reject t
 he edge. When an edge is accepted\, the edges adjacent to it are discarded
 . The goal is to construct as large (heavy) a matching as  possible.\nThe
  complexity of the problem is settled for deterministic algorithms. For ra
 ndomized algorithms\,  a lower bound of $1.693$ on the competitive ratio 
 is known for MCM with a trivial upper bound of two\;  an upper bound of $
 5.356$ is known for MWM. We initiate a systematic study of the same in thi
 s paper with an aim to isolate and understand the difficulty. We begin wit
 h  a primal-dual analysis of the deterministic algorithm due to McGregor.
  All deterministic lower bounds are on instances which are trees at  ever
 y step. Using a considerable extension of the (simple) primal-dual analysi
 s of the deterministic case\, we show a randomized algorithm that is $\\fr
 ac{28}{15}$-competitive for this class of (unweighted) graphs.\nIn the fir
 st talk\, we will review the background and earlier results. In the second
  talk\, we will describe our randomized algorithm. We will also present ot
 her related results if time permits (based on joint work with Ashish Chipl
 unkar and Sundar Vishwanathan: http://arxiv.org/abs/1412.8615.)\n
URL:https://www.tcs.tifr.res.in/web/events/667
DTSTART;TZID=Asia/Kolkata:20160330T100000
DTEND;TZID=Asia/Kolkata:20160330T110000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR