Research map / Bandits and online learning / Online convex optimization and games
Faster Matchings via Learned Duals
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| warm-start Hungarian with learned duals instead of zero duals | Hungarian algorithm · type model, batch (l=50, v up to 300) | iteration count | Improved |
| warm-start with learned duals under extreme noise (v up to 2^20) | Hungarian algorithm · type model, batch, geometric v | iteration count | No clear effect |
| warm-start with learned duals on clustering-derived real instances | Hungarian algorithm · UCI datasets, k=500, batch | iteration count: greater than 2x improvement | Improved |
| learn duals online from previous instances | Hungarian algorithm · type model l=100 v=200, online | run time / iterations | Improved |
| learn duals online on KDD and Covertype (k=500) | Hungarian algorithm · KDD, Covertype, online | iterations | Improved |
| make the instance distribution more concentrated (lower noise variance) (ablation) | Learned Duals · type model | iteration count | Improved |
| use a non-concentrated distribution with little to learn (ablation) | Learned Duals · type model with high variance | iteration count | No clear effect |
| add feasibility-recovery step to learned duals (ablation) | Learned Duals · runtime | extra running time | No clear effect |
Closest papers by meaning
- Faster Fundamental Graph Algorithms via Learned Predictions (ICML 2022 · similarity 0.91)
- Learning-Augmented Online Bipartite Fractional Matching (NeurIPS 2025 · similarity 0.88)
- Secretary and Online Matching Problems with Machine Learned Advice (NeurIPS 2020 · 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)
- Online bipartite matching with imperfect advice (ICML 2024 · similarity 0.85)
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.
