Online Dependent Rounding Schemes for Bipartite Matchings, with Applications

We introduce the abstract problem of rounding an unknown fractional bipartite b-matching bfx 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 M, which is the minimum over all fractional b-matchings bfx, and edges e, of the ratio Pr[e∈ M]/xe. In analogy with the highly influential offline dependent rounding schemes of Gandhi et al.~(FOCS'02, JACM'06), we refer to such algorithms as online dependent rounding schemes (ODRSes). This problem, with additional restrictions on the possible inputs bfx, has played a key role in recent developments in online computing. We provide the first generic b-matching ODRSes that impose no restrictions on bfx. Specifically, we provide ODRSes with rounding ratios of 0.646 and 0.652 for b-matchings and simple matchings, respectively. This breaks the natural barrier of 1-1/e, prevalent for online matching problems, and numerous online problems more broadly. Using our ODRSes, we provide a number of algorithms with similar better-than-(1-1/e) ratios for several problems in online edge coloring, stochastic optimization, and more. Our techniques, which have already found applications in several follow-up works (Patel and Wajc SODA'24, Blikstad et al.~SODA'25, Braverman et al.~SODA'25, and Aouad et al.~2024), include periodic use of offline contention resolution schemes (in online algorithm design), grouping nodes, and a new scaling method which we call group discount and individual markup.