<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Talk by Vijay Vazirani next week on "Online Bipartite Matching and Adwords”, which may be of interest.<div class=""><br class=""></div><div class="">Tuesday 9/27, 12:10 pm @ Harper Center (Booth) room 3B. Please see details below. <div><br class=""></div><div>Best,</div><div>Madhur </div><div><br class=""><blockquote type="cite" class=""><div class="">Begin forwarded message:</div><br class="Apple-interchange-newline"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">From: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">Rad Niazadeh <<a href="mailto:rad.niazadeh@chicagobooth.edu" class="">rad.niazadeh@chicagobooth.edu</a>><br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">Subject: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class=""><b class="">Vijay Vazirani in Booth OM seminar next week!</b><br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">Date: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">September 22, 2022 at 8:22:45 PM CDT<br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">To: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">Madhur Tulsiani <<a href="mailto:madhurt@ttic.edu" class="">madhurt@ttic.edu</a>><br class=""></span></div><br class=""><div class=""><meta http-equiv="Content-Type" content="text/html; charset=utf-8" class=""><div dir="ltr" class=""><p class="MsoNormal"><br class=""></p><p class="MsoNormal">---------------------------------</p><p class="MsoNormal">The Autumn 2022 Workshop in Operations/Management Science begins next week, <b class="">Tuesday, September 27, at 12:10 p.m. CT in the Harper Center room 3B. </b><span class="">Vijay</span> <span class="">Vazirani</span> will present “<span style="background-position: initial initial; background-repeat: initial initial;" class="">Online Bipartite Matching and Adwords</span>.” This presentation will be based on two papers, linked <a href="https://arxiv.org/abs/2107.10777" class="">here</a> and <a href="https://www.ics.uci.edu/~vazirani/Small.pdf" class="">here</a>.<u class=""></u><u class=""></u></p><p class="MsoNormal"><b class=""><span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial" class=""><u class=""></u> <u class=""></u></span></b></p><p class="MsoNormal"><b class=""><span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial" class="">Abstract:</span></b><span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial" class=""> </span>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 <span class="">Vazirani</span>, 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.</p><div class=""><div dir="ltr" data-smartmail="gmail_signature" class=""><div dir="ltr" class=""><p style="margin:0in 0in 0.0001pt;color:rgb(51,51,51);font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px" class=""><span style="font-size:1pt;font-family:Arial,sans-serif;color:rgb(156,29,33)" class=""> </span></p><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><span style="font-weight:700" class=""><span style="font-size:10.5pt;font-family:Arial,sans-serif;color:rgb(156,29,33)" class=""><span style="display:inline" class="">Rad Niazadeh</span></span></span></div><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><span style="font-size:10.5pt;font-family:Arial,sans-serif;color:rgb(156,29,33)" class="">Assistant Professor of Operations Management</span></div><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><span style="font-size:10.5pt;font-family:Arial,sans-serif;color:rgb(156,29,33)" class="">Faculty</span></div><p style="margin:0in 0in 0.0001pt;color:rgb(51,51,51);font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""> </span></p><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class="">The University of Chicago</span></div><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class="">Booth School of Business</span></div><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""><span style="display:inline" class="">5807 South Woodlawn Avenue, HC-303</span></span></div><p style="margin:0in 0in 0.0001pt;color:rgb(51,51,51);font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""></span></p><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""><span style="display:inline" class="">Chicago,</span></span> <span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""><span style="display:inline" class="">Illinois</span></span> <span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""><span style="display:inline" class="">60637</span></span></div><p style="margin:0in 0in 0.0001pt;color:rgb(51,51,51);font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""></span></p><p style="margin:0in 0in 0.0001pt;color:rgb(51,51,51);font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""> </span></p><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""><span style="display:inline" class="">Website: <a href="https://faculty.chicagobooth.edu/rad-niazadeh" target="_blank" class="">https://faculty.chicagobooth.edu/rad-niazadeh</a><br class=""></span></span></div><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""><span style="display:inline" class="">Phone: 773-834-6247</span></span></div><p style="margin:0in 0in 0.0001pt;color:rgb(51,51,51);font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""></span></p><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""><span style="display:inline" class="">Mobile: 607-379-5744</span></span></div><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><br class=""></div><div style="margin: 0in 0in 0.0001pt; color: rgb(51, 51, 51); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;" class=""><a href="https://www.chicagobooth.edu/" style="background-color:transparent;color:rgb(51,122,183);border:0px" target="_blank" class=""><img src="https://statcontent.chicagobooth.edu/Static/BUSAssets/EmailSignature/Assets/Images/ChicagoBoothMain.png" alt="" style="border:0px;vertical-align:middle" class=""></a></div><p style="margin:0in 0in 0.0001pt;color:rgb(51,51,51);font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""> </span><span style="color:rgb(103,110,115);font-family:Times,serif;font-size:10.5pt" class=""> </span></p><p style="margin:0in 0in 0.0001pt;color:rgb(51,51,51);font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:14px" class=""><span style="font-size:10.5pt;font-family:Times,serif;color:rgb(103,110,115)" class=""> </span></p></div></div></div></div>
</div></blockquote></div><br class=""></div></body></html>