Theory Group Seminar

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