DRAFT
Caltech Logo

Theory Group Seminar

Thursday, October 21, 2021
3:00pm to 4:00pm
Add to Cal
Annenberg 105
Online Bipartite Matching and Adwords
Vijay Vazirani, Distinguished Professor, Computer Science, UC, Irvine,

Over the last three decades, the online bipartite matching (OBM) problem has emerged as a central problem in the area of Online Algorithms. Perhaps even more important is its role in the area of Matching-Based Market Design. The recent 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 a 1990 joint paper with Richard Karp and Umesh Vazirani, we gave an optimal 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. We will start by presenting a "textbook quality" proof of RANKING. We will then provide a broad overview of the area of Matching-Based Market Design and pinpoint the role of OBM.

The simplicity of the new proof of RANKING raises the possibility of extending it all the way to a generalization of OBM called the adwords problem. This problem is both notoriously difficult and very significant, the latter because it captures a key computational issue arising in Google's AdWords market. If time remains, we will show how far this endeavor has gone and what remains

For more information, please contact Linda Taddeo by phone at 626-395-6704 or by email at ltaddeo@caltech.edu.