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.