Tata Institute of Fundamental Research
Online Matchings and Online Advertising
Seminar
Speaker:
Nitish Korula
Department of Computer Science
University of Illinois at Urbana-Champaign
3240, Siebel Center
2
Date:
Thursday, 29 Oct 2009 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
In a variety of contexts related to Internet advertising, online versions of classic problems such as maximum-weight bipartite matching arise. With internet advertising becoming a multi-billion dollar business, there is a need for algorithms to solve these problems effectively. However, without assumptions on the input distribution, edge weights, order of arrival, etc., no online algorithms for these problems can achieve any bounded competitive ratio.
Fortunately, in many of the advertising contexts where these problems need to be solved, they do satisfy one or more of these assumptions. In this talk, I will present a collection of algorithms with competitive ratios ranging from 1/8 to 1-1/e to 1-\\epsilon, solving problems in ad reservation, display advertising, etc. They also have connections to other well-known problems such as the classical Secretary problem and the Generalized Assignment Problem (GAP). Our algorithms are simple and efficient, making online decisions in essentially linear time (joint work with Martin Pal, Jon Feldman, Vahab Mirrokni, and S. Muthu Muthukrishnan).
| Speaker: | Nitish Korula Department of Computer Science University of Illinois at Urbana-Champaign 3240, Siebel Center 2 |
| Date: | Thursday, 29 Oct 2009 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
In a variety of contexts related to Internet advertising, online versions of classic problems such as maximum-weight bipartite matching arise. With internet advertising becoming a multi-billion dollar business, there is a need for algorithms to solve these problems effectively. However, without assumptions on the input distribution, edge weights, order of arrival, etc., no online algorithms for these problems can achieve any bounded competitive ratio.
Fortunately, in many of the advertising contexts where these problems need to be solved, they do satisfy one or more of these assumptions. In this talk, I will present a collection of algorithms with competitive ratios ranging from 1/8 to 1-1/e to 1-\\epsilon, solving problems in ad reservation, display advertising, etc. They also have connections to other well-known problems such as the classical Secretary problem and the Generalized Assignment Problem (GAP). Our algorithms are simple and efficient, making online decisions in essentially linear time (joint work with Martin Pal, Jon Feldman, Vahab Mirrokni, and S. Muthu Muthukrishnan).
Fortunately, in many of the advertising contexts where these problems need to be solved, they do satisfy one or more of these assumptions. In this talk, I will present a collection of algorithms with competitive ratios ranging from 1/8 to 1-1/e to 1-\\epsilon, solving problems in ad reservation, display advertising, etc. They also have connections to other well-known problems such as the classical Secretary problem and the Generalized Assignment Problem (GAP). Our algorithms are simple and efficient, making online decisions in essentially linear time (joint work with Martin Pal, Jon Feldman, Vahab Mirrokni, and S. Muthu Muthukrishnan).