Doctoral Thesis: Online Allocation Algorithms with Applications in Computational Advertising


Event Speaker: 

Morteza Zadimoghaddam

Event Location: 


Event Date/Time: 

Friday, December 6, 2013 - 12:00pm


Over the last few decades, a wide variety of allocation markets emerged from the
Internet and introduced interesting algorithmic challenges, e.g., ad auctions, online
dating markets, matching skilled workers to jobs, etc. I focus on the use of allocation
algorithms in computational advertising as it is the quintessential application of my
research. I will also touch on the classic secretary problem with submodular utility
functions, and show that how it is related to advertiser's optimization problem in
computational advertising applications. In all these practical situations, we should
focus on solving the allocation problems in an online setting since the input is being
revealed during the course of the algorithm, and at the same time we should make
irrevocable decisions. We can formalize these types of computational advertising
problems as follows. We are given a set of online items, arriving one by one, and a
set of advertisers where each advertiser specifies how much she wants to pay for each
of the online items. The goal is to allocate online items to advertisers to maximize
some objective function like the total revenue, or the total quality of the allocation.
There are two main classes of extensively studied problems in this context: budgeted
allocation (a.k.a. the adwords problem) and display ad problems. Each advertiser is
constrained by an overall budget limit, the maximum total amount she can pay in
the first class, and by some positive integer capacity, the maximum number of online
items we can assign to her in the second class.
Thesis Supervisor: Erik D. Demaine