Talks & Seminars
Title: Algorithmic Issues in Indivisible Allocations
Dr. Deeparnab Chakrabarty, University of Pennsylvania, Philadelphia.
Date & Time: August 9, 2010 14:00
Venue: KR Conference Room
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.
Speaker Profile:
Deeparnab is a Post Doctoral Fellow at Department of Computer and Information Sciences, School of Engineering and Applied Sciences, University of Pennsylvania, Philadelphia. He did his PhD at Georgia Tech and his B Tech from our department.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback