Metraipolis › archive › dc_1b33c077caaa
Consistency-Robustness Tradeoffs for Online Bipartite Allocation with Multiple Stages — arXiv:2609.15837
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.15837
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T02:15:37.359Z
- SHA-256 of the archived text
b27598d33f59ca793a72e55326005468666bd47ae0e52b823beea9c7fcf2bb2f- Stable URL of this page
https://metraipolis.com/documento/dc_1b33c077caaa
How to cite
Consistency-Robustness Tradeoffs for Online Bipartite Allocation with Multiple Stages — arXiv:2609.15837 — arXiv (en), https://arxiv.org/abs/2609.15837 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1b33c077caaa (Metraipolis archive dc_1b33c077caaa, sha256 b27598d33f59ca793a72e55326005468666bd47ae0e52b823beea9c7fcf2bb2f)
BibTeX
@misc{dc1b33c077caaa,
title = {Consistency-Robustness Tradeoffs for Online Bipartite Allocation with Multiple Stages — arXiv:2609.15837},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.15837},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1b33c077caaa; sha256 b27598d33f59ca793a72e55326005468666bd47ae0e52b823beea9c7fcf2bb2f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15837. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study learning-augmented online bipartite allocation with multiple stages. In the $k$-stage vertex-weighted fractional bipartite matching problem, demand vertices arrive in $k$ stages, and the algorithm receives possibly inaccurate predictions of the allocation in each stage. While tight consistency-robustness tradeoffs were known for the two-stage case, no nontrivial tradeoff was known for an arbitrary number of stages. Our main result is the first consistency-robustness tradeoff for $k$-stage vertex-weighted fractional bipartite matching with predictions, for every $k\ge2$. Let $R_k=1-(1-1/k)^k$. For every $R\in[0,R_k]$, our algorithm is $R$-robust and $C_k(R)$-consistent, where $C_k(R)=k(1-R)^{1/k}+R-(k-1)$. This simultaneously recovers the known tight two-stage tradeoff and the optimal prediction-free $k$-stage competitive guarantee $R_k = C_k(R_k)$, while strictly dominating the natural randomized coin-flip baseline between these endpoints. We also present an algorithm for the classical online setting, where demands arrive one by one and the number of demands is unknown in advance. It has a consistency ratio of at least $C_\infty(R)=1+R+\ln(1-R)$ for a given robustness $R\in[0,1-1/e]$, improving the best previously known tradeoff for this problem. Finally, we extend the framework to fractional AdWords and fractional predictions. Our algorithms are based on stage-wise convex programs with carefully calibrated vertex-dependent penalties. The penalties maintain a dynamic safety reserve for each supply vertex, balancing protection against adversarial future arrivals with the ability to exploit the predicted allocation.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.15837 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T01:54:07.138Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).