Research map / Bandits and online learning / Online convex optimization and games
Learning-Augmented Online Bipartite Fractional Matching
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 learning-augmented primal-dual algorithms (LAB for vertex-weighted, PAW for unweighted with integral advice) for online bipartite fractional matching that dominate the coin-flip baseline in robustness-consistency, extends LAB to small-bid AdWords, and proves a hardness bound on the tradeoff.
Problem
Online bipartite fractional matching (vertex-weighted and unweighted) with suggested-matching advice: achieving a robustness-consistency tradeoff that beats the coin-flip strategy across all robustness levels, and understanding the best attainable tradeoff.
Approach
An advice-dependent penalty function in a Balance-style waterfilling algorithm (LAB) that penalizes offline vertices based on both their filled amount and the advice-allocated amount; for the unweighted case, a Push-and-Waterfill procedure first pushes flow along the advised edge up to a level lambda and then waterfills. Analysis uses online primal-dual with a factor-revealing LP based hardness co
Key results
- LAB is r(lambda)-robust and c(lambda)-consistent with r(lambda)=1-e^(lambda-1)-(e^(lambda-1)-lambda)ln(1-lambda e^(1-lambda))-lambda(1-lambda) and c(lambda)=1+lambda-e^(lambda-1), dominating CoinFlip in the vertex-weighted setting.
- PAW for unweighted integral advice achieves r(lambda)=1-(1-lambda+lambda^2/2)e^(lambda-1) robustness and c(lambda)=1-(1-lambda)e^(lambda-1) consistency.
- Experiments show competitive ratios of LAB and PAW start at 1 under perfect advice and degrade smoothly with noise; for large noise, advice-free Balance outperforms both.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use LAB's advice-dependent penalty and tradeoff algorithm rather than CoinFlip | Vertex-weighted online bipartite fractional matching · Vertex-weighted online bipartite fractional matching | robustness-consistency tradeoff | Helped |
| use PAW rather than CoinFlip | Unweighted online bipartite fractional matching with integral advice · Unweighted online bipartite fractional matching | robustness-consistency tradeoff | Helped |
| extend LAB to AdWords under the small bids assumption | AdWords · AdWords with advice, small bids | robustness-consistency tradeoff | Helped |
| increase advice noise parameter gamma | LAB and PAW · Synthetic and real-world graph instances | competitive ratio | Hurt |
| use Balance instead of LAB or PAW when advice noise is sufficiently large | Online matching · Synthetic and real-world graph instances | competitive ratio | Helped |
Surprising findings
- In the unweighted setting, the LAB tradeoff lies below the CoinFlip line because CoinFlip can be 1/2-robust with full consistency, motivating a separate algorithm PAW.
- For sufficiently large advice noise, the advice-free Balance algorithm outperforms both LAB and PAW.
Limitations
- LAB's tradeoff is below CoinFlip in the unweighted setting, so a separate algorithm was needed there.
- PAW is analyzed only for integral advice in the unweighted setting.
- AdWords result holds only under the small bids assumption and loses a factor 1-3 sqrt(eps ln(1/eps)).
Experimental setup
Datasets: synthetic Erdos-Renyi graphs synthetic upper triangular graphs real-world graph instances
Benchmarks: synthetic Erdos-Renyi graphs synthetic upper triangular graphs real-world graph instances
Metrics: competitive ratio robustness consistency
Baselines: CoinFlip Balance Mahdian et al. (2007/2012) AdWords with advice Waterfilling
Builds on: Balance (waterfilling) algorithm Mahdian et al. AdWords with predictions Ranking algorithm CoinFlip baseline
Closest papers by meaning
- Online bipartite matching with imperfect advice (ICML 2024 · similarity 0.91)
- Beyond the Half Approximation: Fair and Efficient Online Class Matching (NeurIPS 2026 · similarity 0.88)
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.87)
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models (ICML 2025 · similarity 0.87)
- Online Budgeted Matching with General Bids (NeurIPS 2024 · similarity 0.86)
- MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation (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.