Georgia Institute of Technology College of Sciences

I will present two related 30-minute talks. Title 1: Generalized Online Matching with Concave Utilities Abstract 1: In this talk we consider a search engine's ad matching problem with soft budget. In this problem, there are two sides. One side is ad slots and the other is advertisers. Currently advertisers are modeled to have hard budget, i.e., they have full utility for ad slots until they reach their budget, and at that point they can't be assigned any more ad-slots. Mehta-Saberi-Vazirani-Vazirani and Buchbinder-J-Naor gave a 1-1/e approximation algorithm for this problem, the latter had a traditional primal-dual analysis of the algorithm. In this talk, we consider a situation when the budgets are soft. This is a natural situation if one models that the cost of capital is convex or the amount of risk is convex. Having soft budget makes the linear programming relaxation as a more general convex programming relaxation. We still adapt the primal-dual schema to this convex program using an elementary notion of convex duality. The approximation factor is then described as a first order non-linear differential equation, which has at least 1-1/e as its solution. In many cases one can solve these differential equations analytically and in some cases numerically to get algorithms with factor better than 1-1/e. Based on two separate joint works, one with Niv Buchbinder and Seffi Naor, and the other with Nikhil Devanur. Title 2: Understanding Karp-Vazirani-Vazirani's Online Matching (1990) via Randomized Primal-Dual. Abstract 2: KVV online matching algorithm is one of the most beautiful online algorithms. The algorithm is simple though its analysis is not equally simple. Some simpler version of analysis are developed over the last few years. Though, a mathematical curiosity still remains of understanding what is happening behind the curtains, which has made extending the KVV algorithm hard to apply to other problems, or even applying to the more general versions of online matching itself. In this talk I will present one possibility of lifting the curtains. We develop a randomized version of Primal-Dual schema and redevelop KVV algorithm within this framework. I will then show how this framework makes extending KVV algorithm to vertex weighted version essentially trivial, which is currently done through a lot of hard work in a brilliant paper of Aggarwal-Goel-Karande-Mehta (2010). Randomized version of Primal-Dual schema was also a missing technique from our toolbox of algorithmic techniques. So this talk also fills that gap.