---

* 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


---

---