[talks] Aman Dhesi Generals: Monday, May 19, 2014 at 2pm in Room 402

[Nicki Gotsis]

Aman Dhesi will present his general exam on Monday, May 19, 2014 at 2pm in Room 402.  His committee members are Moses Charikar, Mark Braverman, and Bernard Chazelle.

Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so.  His abstract and reading list follow below:

Abstract:

Matching problems arise in many contexts - matching jobs to machines, patients to hospitals, ad impressions to advertisers. In general, one class of objects (items) need to be matched to another class of objects (agents) and the agents have some form of preference or utility function over the items.

Our work focuses on the online version of the matching problem, where the items are revealed one-by-one and need to be irrevocably matched as soon as they arrive. We consider a significant generalization of the online matching and budgeted allocation (AdWords) problems, where agents have concave utility functions. Building upon the work of Devanur and Jain who characterize the optimal competitive ratio as the solution to a differential equation, we design a constructive algorithm that is 1-1/e competitive using the primal-dual framework. We also show that if the online input is uniformly randomly ordered, a simple Greedy algorithm is 1-1/e competitive.

This is joint work with Prof. Moses Charikar.

Reading List:

1. (Book) T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009

2. Mehta, A., Saberi, A., Vazirani, U., and Vazirani, V. 2005. Adwords and generalized on-line
matching. In FOCS 05

3. Karp, R. M., Vazirani, U. V., and Vazirani, V. V. 1990. An optimal algorithm for on-line
bipartite matching. In STOC '90

4. Devanur, N. R. and Hayes, T. P. 2009. The adwords problem: online keyword matching with
budgeted bidders under random permutations. In ACM Conference on Electronic Commerce 2009

5. N. Buchbinder, K. Jain, and J. S. Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA’07

6. G. Goel and A. Mehta. Online budgeted matching in random input models with applications to adwords. In SODA ’08

7. N. Devanur, K. Jain and R. Kleinberg. Randomized Primal-Dual Analysis of RANKING
for Online Bipartite Matching. In SODA ‘13

8. G. Aggarwal, G. Goel, C. Karande, and A. Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In SODA 2011

9. N. Devanur, K. Jain. Online Matching with Concave Returns. In STOC 2012

10. N. Devanur, Z. Huang. Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms. In SODA 2014

11. N. Devanur. Online Algorithms with Stochastic Input. In ACM SIGEcom Exchanges, 2011