BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1175
DTSTAMP:20230914T125953Z
SUMMARY:Online Bipartite Matching and Adwords
DESCRIPTION:Speaker: Vijay V. Vazirani (University of California\, Irvine)\
n\nAbstract: \nOver the last three decades\, the online bipartite matching
(OBM) problem has emerged as a central problem in the area of Online Algo
rithms. Perhaps even more important is its role in the area of Matching-Ba
sed Market Design. The resurgence of this area\, with the revolutions of t
he Internet and mobile computing\, has opened up novel\, path-breaking app
lications\, and OBM has emerged as its paradigmatic algorithmic problem.\n
In a 1990 joint paper with Richard Karp and Umesh Vazirani\, we gave an op
timal algorithm\, called RANKING\, for OBM\, achieving a competitive ratio
of (1 – 1/e)\; however\, its analysis was difficult to comprehend. Over
the years\, several researchers simplified the analysis.\nWe will start b
y presenting a “textbook quality” proof of RANKING. Its simplicity rai
ses the possibility of extending RANKING all the way to a generalization o
f OBM called the adwords problem. This problem is both notoriously difficu
lt and very significant\, the latter because of its role in the AdWords ma
rketplace of Google. We will show how far this endeavor has gone and what
remains. We will also provide a broad overview of the area of Matching-Bas
ed Market Design and pinpoint the role of OBM. \nBased on:\nhttps://arxiv
.org/pdf/2107.10777.pdf\nBio: Vijay Vazirani got his undergraduate degree
from MIT in 1979 and his PhD from the University of California\, Berkeley
in 1983. He is currently a Distinguished Professor at the University of Ca
lifornia\, Irvine.\nVazirani has made fundamental contributions to several
areas of the theory of algorithms\, including algorithmic matching theory
\, approximation algorithms and algorithmic game theory\, as well as to co
mplexity theory\, in which he established\, with Les Valiant\, the hardnes
s of unique solution instances of NP-complete problems. Over the last four
years\, he has been working on algorithms for matching markets. He is one
of the founders of algorithmic game theory.\nIn 2001 he published Approxi
mation Algorithms\, which is widely regarded as the definitive book on the
topic. In 2007\, he published the co-edited book Algorithmic Game Theory.
Another co-edited book\, Online and Matching-Based Market Design\, will b
e published by Cambridge University Press in early 2022\; see its flyer:
\nhttps://www.ics.uci.edu/~vazirani/flyer.pdf\n
URL:https://www.tcs.tifr.res.in/web/events/1175
DTSTART;TZID=Asia/Kolkata:20211207T160000
DTEND;TZID=Asia/Kolkata:20211207T170000
LOCATION:in person @ R.No. AG-69 and also via Zoom
END:VEVENT
END:VCALENDAR