From Adwords to Online Matching with Stochastic Rewards, and Back

Date: May 12, 2022
Time: 4:00 pm
Room: DBH 4011
Speaker: Rajan Udwani 
(UC Berkeley)
In this talk, we consider the problem of online matching with stochastic rewards (OMSR) and the setting of Adwords with unknown budgets (AUB). OMSR is a generalization of online bipartite matching (KVV 1990), where each edge has probability of success. When  a  match is made, it succeeds with the probability of the corresponding  edge.  AUB drops a central assumption in the Adwords problem (MSVV 2005), namely that the budgets of offline vertices are known a priori. In both settings, when the online arrival sequence is adversarial, the natural greedy algorithm is 0.5 competitive and finding the best possible competitive ratio guarantee remains open.
Mehta and Panigrahi (2012), showed an equivalence between interesting special cases of these settings. Using (a generalization of) this connection alongside a novel LP free analysis, we discuss our recent progress on these problems leading to state-of-the-art competitive ratio guarantees for both settings. Time permitting, we also discuss other recent applications of our LP free analysis approach.
Partly based on joint work with Vineet Goyal.

Rajan Udwani is an Assistant Professor of Industrial Engineering and Operations Research at UC Berkeley. He holds a B.Tech in Electrical Engineering from IIT Bombay and a PhD in Operations Research from MIT. He also spent a couple of years as a postdoctoral researcher at Columbia UniversityHe works on algorithms for optimization under uncertainty with a focus on revenue management and pricing. His work has been recognized by INFORMS junior faculty and student paper awards.

Close Menu
Skip to content