Revisiting bipartite graph matching

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


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!