BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/669
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: \nAbstract: In this series of two talks\, we will investigate the pow
 er of randomized algorithms for the maximum cardinality matching (MCM) and
  the maximum weight matching (MWM) problems in the online preemptive model
 . In this model\, the edges of a graph are revealed one by one and the alg
 orithm is required to always maintain a valid matching. On seeing an edge\
 , the algorithm has to either accept or reject the edge. When an edge is a
 ccepted\, the edges adjacent to it are discarded. The goal is to construct
  as large (heavy) a matching as  possible.\n\nThe complexity of the probl
 em is settled for deterministic algorithms. For randomized 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 this paper with an aim to i
 solate and understand the difficulty. We begin with  a primal-dual analys
 is of the deterministic algorithm due to McGregor. All deterministic lower
  bounds are on instances which are trees at  every step. Using a consider
 able extension of the (simple) primal-dual analysis of the deterministic c
 ase\, we show a randomized algorithm that is $\\frac{28}{15}$-competitive 
 for this class of (unweighted) graphs.\n\nIn the first talk\, we will revi
 ew the background and earlier results. In the second talk\, we will descri
 be our randomized algorithm. We will also present other related results if
  time permits (based on joint work with Ashish Chiplunkar and Sundar Vishw
 anathan: http://arxiv.org/abs/1412.8615.)\n \n
URL:https://www.tcs.tifr.res.in/web/events/669
DTSTART;TZID=Asia/Kolkata:20160401T160000
DTEND;TZID=Asia/Kolkata:20160401T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR