Optimal Rounding for Two-Stage Bipartite Matching

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 selected from among revealed edges \(E \subseteq B_1 \times I\). In stage two, edges \(E^\theta \subseteq B_2 \times I\) are sampled from a known distribution, and a second matching must be selected between \(B_2\) and unmatched vertices in \(I\). The objective is to maximize the total weight of the combined matching. We design polynomial-time approximations to the optimum online algorithm, achieving guarantees of \(^{{7}}/_{{8}}\) for vertex-weighted graphs and \(2\sqrt{2}-2 \approx 0.828\) for edge-weighted graphs under arbitrary distributions. Both approximation ratios match known upper bounds on the integrality gap of the natural fractional relaxation, improving upon the best-known approximation of \(0.767\) by Feng, Niazadeh, and Saberi for unweighted graphs whose second batch consists of independently arriving nodes.