- Series
- ACO Seminar
- Time
- Thursday, August 25, 2011 - 11:05am for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Kamal Jain – Microsoft Research, Redmond, WA
- Organizer
- Prasad Tetali
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.