Online Dependent Rounding Schemes for Bipartite Matchings, with

We introduce the abstract problem of rounding an unknown fractional bipartite b-matching x revealed online (e.g., output by an online fractional algorithm), exposed node-by-node on one side. The objective is to maximize the rounding ratio of the output matching 𝓜, which is the minimum over all fractional b-matchings x, and edges e, of the ratio Pr[e ∈ 𝓜]/xe. In analogy with the highly influential offline dependent rounding schemes of Gandhi et al. (FOCS’02, J.ACM’06), we refer to such algorithms as online dependent rounding schemes (ODRSes). This problem, with additional restrictions on the possible inputs x, has played a key role in recent developments in online computing.