# Online Dependent Rounding Schemes for Bipartite Matchings, with Applications

arXiv: https://arxiv.org/abs/2301.08680 · HTML: https://mlsanity.com/paper/2301.08680/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jan 2023.

## Built on by (most cited first, 2 of 2)

- [Learning-Augmented Online Bipartite Fractional Matching](https://mlsanity.com/paper/2505.19252/) (2025)
- [MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation](https://mlsanity.com/paper/2406.05959/) (2024)

## Abstract (arXiv)

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.