Optimal Rounding for Two-Stage Bipartite Matching

Tristan Pollner, Amin Saberi, Anders Wikum

We study two-stage bipartite matching, in which the edges of a bipartite graph on vertices $(B_1\cup B_2,I)$ are revealed in two batches. In stage one, a matching must be selecte…