[Paper] Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model

Source: arXiv - 2511.23388v1

Overview

This paper tackles the classic online bipartite matching problem—think of assigning incoming tasks to a fixed pool of workers—in a setting where the order of arrivals is random and the algorithm receives predictions about each incoming vertex’s neighborhood. By blending these predictions with a robust fallback strategy, the authors deliver an algorithm that is both highly consistent when predictions are accurate and reliably competitive when they are not, even when the optimal matching is far from perfect.

Key Contributions

• Generalized learning‑augmented framework: Extends prior work to handle any optimal matching size, requiring only that the predicted matching covers a constant fraction α of the offline side.
• Dual‑performance guarantees: Achieves near‑optimal consistency (≈ 1) when predictions are correct and retains the classic β‑robustness (the best known competitive ratio for the random‑order model) when they are misleading.
• Smooth trade‑off: Proves that the competitive ratio degrades gracefully as prediction error grows, providing a continuous spectrum between consistency and robustness.
• Algorithmic simplicity: Uses a short “sample prefix” of arrivals to test prediction quality, then either follows the predictions or switches to a well‑studied baseline algorithm (e.g., the Ranking algorithm).
• Theoretical analysis: Provides rigorous bounds that hold for any constant α ∈ (0, 1] and any error level, without assuming a perfect offline‑online match.

Methodology

1. Prediction model: Each online vertex arrives with a predicted neighborhood (its set of possible offline matches). The predictions may be noisy or even adversarial.
2. Sample‑and‑test phase: The algorithm observes the first γ · n arrivals (γ ≪ 1) as a sample. It compares the actual neighborhoods seen to the predicted ones, estimating the overall prediction error.
3. Decision rule:
   • If the error estimate is below a chosen threshold, the algorithm trusts the predictions and greedily matches each new vertex according to the predicted optimal matching (which is guaranteed to be at least α n large).
   • Otherwise, it discards the predictions and runs a β‑competitive baseline (e.g., the classic Ranking algorithm) on the remaining arrivals.
4. Analysis technique: The authors bound the probability that the sample misclassifies the prediction quality, then combine the performance of the two branches. By carefully setting γ and the error threshold, they ensure that the loss from a wrong decision is only a lower‑order term (the “‑o(1)” in the guarantees).

Results & Findings

• Consistency: When predictions are accurate (error → 0), the algorithm matches almost every vertex that the optimal offline solution would, achieving a competitive ratio of 1 − o(1).
• Robustness: In the worst case (predictions completely untrustworthy), the algorithm falls back to the baseline and guarantees a competitive ratio of β − o(1), where β is the best known bound for random‑order online bipartite matching (≈ 0.632 for unweighted graphs).
• Smooth degradation: For intermediate error levels ε, the competitive ratio interpolates between the two extremes, roughly following a function f(ε) = (1 − ε)·(1 − o(1)) + ε·(β − o(1)). This shows that modest prediction errors only cause modest performance loss.
• No optimal‑size assumption: Unlike prior work, the analysis does not require the optimal matching to be perfect (size n). It works even when the true optimum is much smaller, as long as the predicted matching is at least a constant fraction α of n.

Practical Implications

• Task scheduling & load balancing: Systems that receive a stream of jobs (online vertices) and have a pool of servers (offline vertices) can feed ML‑generated affinity scores as predictions. The algorithm will exploit good predictions to achieve near‑optimal throughput while safely reverting to a proven online heuristic if the model drifts.
• Ad‑allocation & recommendation: In real‑time ad auctions or content recommendation, predictions about user interests can be treated as neighborhoods. The approach guarantees high revenue when predictions are reliable, yet protects against sudden changes in user behavior.
• Edge‑computing resource assignment: Devices connecting to edge nodes often provide estimated connectivity profiles. Using this learning‑augmented matching, edge orchestrators can quickly assign tasks with confidence, falling back to a robust matching when network conditions are misestimated.
• Implementation simplicity: The algorithm only needs a short observation window and a basic baseline matcher, making it easy to plug into existing pipelines that already use Ranking or Greedy matchers.

Limitations & Future Work

• Prediction quality metric: The analysis assumes access to a global error estimate derived from the sample; designing practical, low‑overhead estimators for real systems remains an open challenge.
• Constant‑factor overhead: The “‑o(1)” terms hide factors that depend on the sample size γ and the error threshold; tuning these parameters for specific workloads may require empirical calibration.
• Extension to weighted or multi‑edge settings: The current work focuses on unweighted bipartite graphs. Adapting the framework to weighted matchings or to settings where vertices can be matched multiple times (e.g., load‑sharing) is a natural next step.
• Adaptive adversaries: The random‑order model mitigates worst‑case arrival sequences, but in environments where arrivals can be adversarially correlated with prediction errors, stronger robustness guarantees may be needed.

Overall, the paper pushes learning‑augmented online algorithms closer to real‑world applicability by relaxing restrictive assumptions and offering a clear, performance‑driven pathway for developers to harness predictive models without sacrificing worst‑case guarantees.

Authors

• Kunanon Burathep
• Thomas Erlebach
• William K. Moses

Paper Information

• arXiv ID: 2511.23388v1
• Categories: cs.LG, cs.DS
• Published: November 28, 2025
• PDF: Download PDF