Spring 2011 Seminar Series

DATE: April 14th
LOCATION: E62-550
TIME: 4:15pm
Reception immediately following in the same room

SPEAKER:
Kamal Jain

TITLE
Generalized Online Matching with Concave Utilities

ABSTRACT
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.

 

Credits: This work is based on many collaborations. Collaborators include: Mark Braverman, Niv Buchbinder, Nikhil Devanur, and Seffi Naor