Ramanujan Auditorium

Online Bipartite Matching and Adwords

Vijay Vazirani

University of California, Irvine, USA

Abstract:
Over the last three decades, online bipartite matching (OBM) has emerged as a central problem in the area of Online Algorithms. Perhaps even more important is its role in Matching-Based Market Design. The resurgence of this area, with the revolutions of the Internet and mobile computing, has opened up novel, path-breaking applications, and OBM has emerged as its paradigmatic algorithmic problem. In this talk, we will discuss a simple optimal OBM algorithm and its generalization to the notoriously hard Adwords problem. We will also provide a broad overview of the area of Matching-Based Market Design and pinpoint the role of OBM.

This lecture will also be streamed live to the Public via YouTube.
YouTube Live Stream Link: www.youtube.com/watch?v=PZ8oRce-zEU

More information on Azadi Ka Amrit Mahotsav events conducted by IMSc is available at: www.imsc.res.in/akam/

Speaker Biography:
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 California, Irvine. Vazirani 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 complexity theory, in which he established, with Les Valiant, the hardness 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. In 2001 he published Approximation 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 be published by Cambridge University Press in early 2022; see its flyer: www.ics.uci.edu/~vazirani/flyer.pdf