Online Matching with Stochastic Rewards
- Series
- Graph Theory Seminar
- Time
- Tuesday, February 19, 2013 - 12:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Debmalya Panigrahi – Duke University
The online matching problem has received significant attention in recent years because of its connections to allocation problems in internet advertising, crowd sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations; rather it is to maximize the number of “successful” allocations, where success of an allocation is governed by a stochastic event that comes after the allocation. These applications motivate us to introduce stochastic rewards in the online matching problem. In this talk, I will formally define this problem, point out its connections to previously studied allocation problems, give a deterministic algorithm that is close to optimal in its competitive ratio, and describe some directions of future research in this line of work. (Based on joint work with Aranyak Mehta.)