- Time
- 1:30 – 2:20pm, Tuesday, February 23, 2010
- Place
- CSE 305
- Speaker
- Nikhil Devanur, Microsoft Research - Redmond
## Abstract

Bipartite matching is one of the most basic problems in combinatorial
optimization. We consider a variant of this problem on lopsided bipartite graphs
that arises in a context related to selling online display ads. One
side corresponds
to all the eyeballs and the other side to all the advertisers. There
is an edge when
an advertiser wants to reach an eyeball, aka, ad targeting. The graph
is lopsided
because there are only a small number of advertisers but a large
number of eyeballs.
Every advertiser needs a certain number of eyeballs and every eyeball can be
assigned to one advertiser. The scale involved in this application is
such that the
classical algorithms cannot be used here. We give algorithms which have running
time proportional to the size of the smaller side, i.e., the number of
advertisers.
We also show how to succinctly represent a matching, again the size of
representation only depends on the smaller side. The succinct representation
is obtained from a Linear Program that has a very intriguing property:
the optimal
solution to the LP is guaranteed to contain an optimal fractional matching, but
does not contain an optimal integral matching unless it is unique. In
other words,
this LP is not always a relaxation!