|
|
 |
 News
Colloquia
Optimization Problems in Internet Advertising
Clifford Stein
Columbia University
May 6, 2011
AE 215- 4:00 p.m. to 5:00 p.m.
Abstract:
The use of the internet has led to the creation of fundamentally new forms of
advertising. In turn, this advertising provides the financial support for many
on-line companies and technological breakthroughs.
The development of online advertising has raised many new questions in
economics, mathematics, computer science and engineering, particularly
around the design of auctions and markets, and in the design of
algorithms to efficiently manage them.
Several problems of deciding which ads should be shown to users can be
framed as online stochastic packing integer programs.
In this talk, we will discuss results
on solving these problems from theoretical and practical standpoints.
We first present a near-optimal online algorithm for a general class
of packing integer programs which model various online resource
allocation problems including online variants of routing, ad
allocations, generalized assignment, and combinatorial auctions. As
our main theoretical result, we prove that a simple dual
training-based algorithm achieves a $(1-o(1))$-approximation guarantee
in the random order stochastic model.
We then focus on the online display ad allocation problem and study
the efficiency and fairness of various training-based and online
allocation algorithms
on data sets collected from real-life display ad allocation system.
Our experimental evaluation confirms the effectiveness of
training-based algorithms on real data sets, and also indicates an
intrinsic trade-off between fairness and efficiency.
This talk presents joint work with Jon Feldman, Nitish Korula, Vahab
Mirrokni and Monika Henzinger.
Hosted by: Dr. Elliot Anshelevich (x6491)
Last updated: April 7, 2011
|
|
|
|
