Research map / Graph learning / Graph algorithms and clustering
(Optimal) Online Bipartite Matching with Degree Information
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use expected offline degrees to prioritize lower-degree unmatched neighbors | Online bipartite matching on CLV-B graphs · CLV-B | matching-size distribution | Helped |
| Use degree predictions from the first graph | MinPredictedDegree · Oregon | empirical competitive ratio: ∼ 0.99 vs 0.95 to 0.97 | Helped |
| Use degree predictions from the first graph of each year | MinPredictedDegree · CAIDA | empirical competitive ratio: greater than 0.98 vs around 0.95 | Helped |
| Use expected-degree predictions instead of random priorities | Online matching on symmetric CLV-B with Zipf degrees · Zipf α=0.8 | empirical competitive ratio: ∼ 0.93 vs ∼ 0.86 | Helped |
| Decrease the fraction of online nodes sampled to estimate offline degrees (ablation) | MinPredictedDegree · Symmetric CLV-B, Zipf exponent 1 | empirical competitive ratio | Hurt |
| Use predictions based on only 10% or 1% of online nodes rather than expected degrees (ablation) | MinPredictedDegree · Symmetric CLV-B, Zipf exponent 1 | empirical competitive ratio relative to Ranking | Helped |
| Add the MPD matching rule to known i.i.d. algorithms (ablation) | Known i.i.d. online baselines · Known i.i.d. datasets | empirical competitive ratio | Helped |
| Replace expected-degree predictions with noisy predictions (ablation) | MinPredictedDegree on CLV-B graphs · CLV-B | matching size: at most n - LIS(p[σ]) fewer nodes | Hurt |
| Use perfect actual-degree predictions instead of predictions from earlier graphs (ablation) | MinPredictedDegree · Oregon and CAIDA | empirical competitive ratio | Helped |
Closest papers by meaning
- Online bipartite matching with imperfect advice (ICML 2024 · similarity 0.90)
- Learning-Augmented Online Bipartite Fractional Matching (NeurIPS 2025 · similarity 0.88)
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models (ICML 2025 · similarity 0.87)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.86)
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.86)
- Online Matching with Stochastic Rewards: Provable Better Bound via Adversarial Reinforcement Learning (ICML 2024 · similarity 0.86)
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.