Online primal dual algorithms for generalized online bipartite matching problems

Abstract

Online bipartite matching, first defined by Karp, Vazirani, and Vazirani (STOC 1990) three decades ago, has received significant attention in recent years due to its many applications including online advertising. I study two well-known generalizations of the problem: online matching with stochastic rewards (FOCS 2012) and AdWords (FOCS 2005). In both problems, I propose online algorithms based on the online primal dual framework by Devanur, Jain, and Kleinberg (SODA 2013), with competitive ratios beating the best previous results. In online matching with stochastic rewards, edges are associated with success probabilities and a match succeeds with the probability of the corresponding edge. I present a 0.572 competitive algorithm for the case of vanishing and unequal probabilities, improving the best previous bound of 0.534 by Mehta, Waggoner, and Zadimoghaddam (SODA 2015) and, in fact, is even better than the best previous bound of 0.567 by Mehta and Panigrahi (FOCS 2012) for the more restricted case of vanishing and equal probabilities. For vanishing and equal probabilities, we get a better competitive ratio of 0.576. Our results further generalize to the vertex-weighted case due to the intrinsic robustness of the randomized online primal dual analysis. In the AdWords problem, the optimal 1 - 1/e competitive ratio has been achieved by Mehta, Saberi, Vazirani, and Vazirani (FOCS 2005) in the special case of small bids. It has been open ever since whether there is an algorithm for general bids better than the 0.5-competitive greedy algorithm. I present a 0.5016-competitive algorithm for AdWords, answering this open question on the positive end.