Research map / Optimization / Distributed and compressed
Stochastic Matching via Local Sparsification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a two-stage local sparsification for stochastic bipartite matching: each arriving request uses VarOpt sampling on LP-derived weights to keep k edges, and a coordinator computes the max matching; theory bounds the preservation ratio via a heavy-light decomposition.
Problem
Online stochastic bipartite matching requires irrevocable local decisions, but in decentralized systems the bottleneck is local communication budget; how to prune each request's compatible edges to k while preserving the expected global maximum matching size.
Approach
Local VarOpt sampling of k edges per arriving request, with weights taken from a fractional Expected Instance LP solution (estimated via Monte Carlo), plus a heavy-light analysis showing that if the fractional solution is well spread, the sparsifier preserves matching size up to 1-epsilon with k = epsilon^-2.
Key results
- On the Partitioned Block graph, VarOpt sparsifier with k=10 achieves 99.97% ± 0.04% efficiency versus 82.82% for KVV.
- On the Bahmani 0.901 bound graph, VarOpt with k=10 reaches 99.26% ± 0.17%, exceeding the claimed 0.901 online barrier.
- On NYC taxi data, the VarOpt sparsifier with k=10 closely approaches the offline optimal matching in unmet demand.
Surprising findings
- On the TSM Tightness graph, the random subgraph with k=3 (98.13%) outperforms the VarOpt sparsifier with k=3 (97.54%), and KVV is only 94.58%.
- The MGS baseline performs worst on most synthetic graphs (about 69-75%), below KVV and the random subgraph.
Limitations
- The 1-epsilon guarantee requires the fractional solution to be well spread (small heavy component), which the paper concedes may not hold in general.
- Gap between E[|M(G_S)|] and E[|M(G)|] on graphs with unavoidable heavy edges is left open.
- Results on NYC data and synthetic graphs are simulation-based with 100 vertices per side and no theoretical treatment of heavy edges.
Experimental setup
Datasets: NYC Yellow Taxi Trip Data (May 14, 2025) synthetic adversarial graphs (Partitioned Block, TSM Tightness, KVV Upper Triangular, Bahmani-Kapralov)
Benchmarks: NYC taxi ride-hailing simulation Partitioned Block graph TSM Tightness graph KVV Upper Triangular graph Bahmani-Kapralov 0.901 bound graph
Metrics: matching efficiency / approximation ratio unmet demand
Baselines: KVV Ranking Random Subgraph MGS algorithm Optimal Offline (Hopcroft-Karp)
Builds on: Karp-Vazirani-Vazirani ranking VarOpt sampling Expected Instance LP Two Suggested Matchings
Closest papers by meaning
- Online Matching with Stochastic Rewards: Provable Better Bound via Adversarial Reinforcement Learning (ICML 2024 · similarity 0.86)
- MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation (ICML 2024 · similarity 0.86)
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models (ICML 2025 · similarity 0.84)
- Stochastic Matching Bandits with Rare Optimization Updates (NeurIPS 2026 · similarity 0.84)
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.83)
- FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.