[Theory] Fwd: Vijay Vazirani in Booth OM seminar next week!

[Madhur Tulsiani]

Talk by Vijay Vazirani next week on "Online Bipartite Matching and Adwords”, which may be of interest.

Tuesday 9/27, 12:10 pm @ Harper Center (Booth) room 3B. Please see details below. 

Best,
Madhur 

> Begin forwarded message:
> 
> From: Rad Niazadeh <rad.niazadeh at chicagobooth.edu>
> Subject: Vijay Vazirani in Booth OM seminar next week!
> Date: September 22, 2022 at 8:22:45 PM CDT
> To: Madhur Tulsiani <madhurt at ttic.edu>
> 
> 
> 
> ---------------------------------
> 
> The Autumn 2022 Workshop in Operations/Management Science begins next week, Tuesday, September 27, at 12:10 p.m. CT in the Harper Center room 3B. Vijay Vazirani will present “Online Bipartite Matching and Adwords.” This presentation will be based on two papers, linked here <https://arxiv.org/abs/2107.10777> and here <https://www.ics.uci.edu/~vazirani/Small.pdf>.
> 
>  
> 
> Abstract: 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 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 for OBM, called RANKING, 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. Its simplicity raises the possibility of extending RANKING all the way to a generalization of OBM called the adwords problem. This problem is both notoriously difficult and very significant, the latter because of its role in the AdWords marketplace 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-Based Market Design and pinpoint the role of OBM.
> 
>  
> Rad Niazadeh
> Assistant Professor of Operations Management
> Faculty
>  
> The University of Chicago
> Booth School of Business
> 5807 South Woodlawn Avenue, HC-303
> Chicago, Illinois 60637
>  
> Website:  https://faculty.chicagobooth.edu/rad-niazadeh <https://faculty.chicagobooth.edu/rad-niazadeh>
> Phone: 773-834-6247
> Mobile: 607-379-5744
> 
>  <https://www.chicagobooth.edu/>
>   
>  

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220922/53d81f3b/attachment.html>