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