Online Bipartite Matching With Unknown Distributions

We consider the online bipartite matching problem in the unknown distribution input model. We show that the RANKING algorithm of [KVV90] achieves a competitive ratio of at least 0.653. This is the first analysis to show an algorithm which breaks the natural 1 - 1/e 'barrier' in the unknown distribution model (our analysis in fact works in the stricter, random order model) and answers an open question in [GM08]. We also describe a family of graphs on which RANKING does no better than 0.727 in the random order model. Finally, we show that for graphs which have k > 1 disjoint perfect matchings, RANKING achieves a competitive ratio of at least 1- root 1/k - 1/k(2) + 1/n - in particular RANKING achieves a factor of 1 - o(1) for graphs with omega(1) disjoint perfect matchings.