Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - August 2
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - August 2
Event date: Tuesday, August 02, 2011, at 3:10 PM
Location: GB 244
Title: Prophet-Inequality Setting with Applications to Ad Allocation
Speaker: Mohammad T. Hajiaghayi: Univ. of Maryland at College Park
Abstract:
We study the problem of online stochastic budgeted matching in bipartite graphs. There has been a recent trend of work improving the bound of 1-1/e, most of them motivated by problems related to ``Online Ad Allocation'' and almost all of them considering a 1-1 matching. In this paper, we consider a weighted/budgeted model in which each edge has a weight (i.e., bid of each bidder for each query) and each vertex on the fixed side of the graph has a budget (i.e., total budget of each bidder). The weight of a matching is the minimum of the budget of each vertex and the total weight of edges matched to it when summed over all vertices. We consider this model in a more realistic
stochastic setting where we know the distribution of the incoming queries in advance. We show that if the bid to the budget ratio of every bidder is at most 1/k then the natural randomized online algorithm which is based on solving a fractional LP for the expected instance has an approximation ratio of 1-k^k/e(^k k!) or about 1-\1/{sqrt{2 \pi k} compared to the optimal offline. We also consider a model in which the bidders do not have a budget. Each bidder may have a capacity (i.e., an upper bound on the number of ads that can be allocated to him). We present an algorithm with a tight approximation ratio of 1/2 for this setting which generalizes the classic Prophet Inequality and
has applications in ``Display Ad Auctions''.
Finally we mention the applications of the prophet-inequality setting above for ``AdCell Auction'', a new model of auctions using cell-phone locations and SMS/MMS messaging.