# Stochastic Matching via Local Sparsification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 14 of 14)

- [Online Matching with General Arrivals](https://mlsanity.com/paper/1904.08255/) (2019)
- [Improved Bound for Matching in Random-Order Streams](https://mlsanity.com/paper/2005.00417/) (2020)
- [Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model](https://mlsanity.com/paper/2007.12823/) (2020)
- [Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model](https://mlsanity.com/paper/2103.11669/) (2021)
- [Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints](https://mlsanity.com/paper/1307.2696/) (2013)
- [Towards a Better Understanding of Randomized Greedy Matching](https://mlsanity.com/paper/1907.05135/) (2019)
- [Beating Two-Thirds For Random-Order Streaming Matching](https://mlsanity.com/paper/2102.07011/) (2021)
- [Approximating Maximum Matching Requires Almost Quadratic Time](https://mlsanity.com/paper/2406.08595/) (2024)
- [Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis](https://mlsanity.com/paper/2503.04196/) (2025)
- [Edge-weighted Matching in the Dark](https://mlsanity.com/paper/2507.19366/) (2025)
- [Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance](https://mlsanity.com/paper/2510.16351/) (2025)
- [Improved Approximation for Ranking on General Graphs](https://mlsanity.com/paper/2511.06504/) (2025)
- [A Simple Analysis of Ranking in General Graphs](https://mlsanity.com/paper/2511.08801/) (2025)
- [A Unified Framework for Analysis of Randomized Greedy Matching Algorithms](https://mlsanity.com/paper/2604.00331/) (2026)

## Abstract (arXiv)

The classic online stochastic matching problem typically requires immediate and irrevocable matching decisions. However, in many modern decentralized systems such as real-time ride-hailing and distributed cloud computing, the primary bottleneck is often local communication bandwidth rather than the timing of the match itself. We formalize this challenge by introducing a two-stage local sparsification framework. In this setting, arriving requests must prune their realized compatibility sets to a strict budget of k edges before a central coordinator optimizes the global matching. This creates a "middle ground" between local information constraints and global optimization utility. We propose a local selection strategy, parametrized by a fractional solution of the expected instance. Theoretically, we quantify the approximation ratio as a function of the solution's em spread. We prove that under sufficient spread, our sparsifier globally preserves the expected size of the maximum matching. Empirically, we demonstrate the robustness of our approach using the New York City ride-hailing datasets and adversarial synthetic benchmarks. Our results show that near-optimal global matching is achievable even with highly constrained local budgets, significantly outperforming standard online baselines.