- Series
- Other Talks
- Time
- Friday, August 20, 2010 - 2:00pm for 1 hour (actually 50 minutes)
- Location
- Klaus 1447
- Speaker
- Kamal Jain – Microsoft Research, Redmond, WA
- Organizer
Please Note: This talk should be non-technical except the last few slides. The talk is based on a work done in collaboration with Denis Charles, Max Chickering, Nikhil Devanur, and Manan Sanghi, all from Microsoft.
Lopsided bipartite graphs naturally appear in advertising setting. One side
is all the eyeballs and the other side is all the advertisers. An edge is
when an advertiser wants to reach an eyeball, aka, ad targeting. Such a
bipartite graph is lopsided because there are only a small number of
advertisers but a large number of eyeballs. We give algorithms which have
running time proportional to the size of the smaller side, i.e., the number
of advertisers. One of the main ideas behind our algorithm and as well as
the analysis is a property, which we call, monotonic quality bounds. Our
algorithm is flexible as it could easily be adapted for different kinds of
objective functions.
Towards the end of the talk we will describe a new matching polytope. We
show that our matching polytope is not only a new linear program describing
the classical matching polytope, but is a new polytope together with a new
linear program. This part of the talk is still theoretical as we only know
how to solve the new linear program via an ellipsoid algorithm. One feature
of the polytope, besides being intriguing, is that it has some notion of
fairness built in. This is important for advertising since if an advertiser
wants to reach 10 million users of type A or type B, advertiser won't
necessarily be happy if we show the ad to 10 million users of type A only
(though it fulfills the advertising contract in a technical sense).