Online bipartite matching

[@ 3pm. 9 Feb, 2010. Old CSE, 2nd floor]

Jagadish M

The input to the problem is a bipartite graph G=(U,V,E), in which vertices in U arrive in on-line fashion. As each vertex u from U arrives, the edges incident on it are revealed. We need to match u to one of the previously unmatched vertices in V. If no such vertex in V exists, then u remains unmatched. The choice of a match, after it is made, is irrevocable. The objective is to maximize the size of matching resulting after the last vertex arrives.

Toy problem:  Let us consider the obvious approach: when u arrives assign it to a some unmatched neighbor. Prove that this strategy will give us a matching that is at least half as good as the optimum.

I'll discuss the paper by Aranyak.et al where they consider the generalized version of the problem; the case where a vertex from V can be matched to multiple vertices from U. They have some cool techniques.