Seminar by Deeparnab Chakrabarty
Algorithmic Issues in Indivisible Allocations
Deeparnab Chakrabarty
University of Pennsylvania
Date: Monday, August 2nd, 2010
Time: 3:00 PM
Venue: CS102.Abstract:
The problem of allocating indivisible resources arises often in Operations Research and Game Theory/Economics. In this talk, I will discuss a few concrete problems which come up in the context of advertisement allocations on the Internet. Subsequently, I will describe efficient algorithms, their performance and their limitations, for these problems.
In particular, I will focus on the maximum budgeted allocation problem which arises in revenue maximization in auctions with budget-constrained agents. Budgets make the problem NP-hard, and I will describe an algorithm which attains 75% of the optimum revenue in polynomial time. This is currently the best known algorithm for this problem. The talk will be completely self-contained.