Metraipolis › archive › dc_241ef25ece5e
The Price of Near-Perfect Consistency in Online Metric Matching with Predictions — arXiv:2608.08653
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.08653
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:16:43.079Z
- SHA-256 of the archived text
e1c3c57b10aa1245d5c47530580f4aa1a1be7965d08b3749cb37fa328fb15fa6- Stable URL of this page
https://metraipolis.com/documento/dc_241ef25ece5e
How to cite
The Price of Near-Perfect Consistency in Online Metric Matching with Predictions — arXiv:2608.08653 — arXiv (en), https://arxiv.org/abs/2608.08653 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_241ef25ece5e (Metraipolis archive dc_241ef25ece5e, sha256 e1c3c57b10aa1245d5c47530580f4aa1a1be7965d08b3749cb37fa328fb15fa6)
BibTeX
@misc{dc241ef25ece5e,
title = {The Price of Near-Perfect Consistency in Online Metric Matching with Predictions — arXiv:2608.08653},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.08653},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_241ef25ece5e; sha256 e1c3c57b10aa1245d5c47530580f4aa1a1be7965d08b3749cb37fa328fb15fa6},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08653. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study online metric matching with per-request action predictions. On the real line, every deterministic $(1+\varepsilon)$-consistent algorithm has robustness at least $1+\sum_{j=1}^{k-1}2^{j+1}/\varepsilon^j$, and we give a deterministic algorithm for arbitrary metrics with the same leading term. Thus, for every fixed $k$, $\lim_{\varepsilon\downarrow 0}\varepsilon^{k-1}R_k^{\mathbb{R}}(1+\varepsilon)=\lim_{\varepsilon\downarrow 0}\varepsilon^{k-1}R_k(1+\varepsilon)=2^k$. The comparison is uniform up to an absolute constant for $0<\varepsilon\le 1/(k-1)$. We determine the two-server trade-off in both settings and the real-line three-server value $1+4/\varepsilon+8/\varepsilon^2$ for $0<\varepsilon\le\sqrt{13}-3$. When the predicted labels are distinct, the algorithm pays at most $(1+\varepsilon)$ times the cost of the predicted matching. For randomised algorithms, the fixed-$k$ dependence remains $\Theta_k(1/\varepsilon^{k-1})$. Uniformly in $k$, robustness is at most $M_0(\varepsilon)\rho_k^0$, where $\rho_k^0$ is the optimal strict prediction-free randomised ratio on the real line and $M_0(\varepsilon)=(2e+o(1))e^{2/\varepsilon}$. For every $\eta>0$, a lower bound $\exp((2-\eta)/\varepsilon)$ holds once $k\ge C_\eta/\varepsilon$. The randomised upper bound follows from a comparison theorem for two online algorithms whose states can be coupled at a cost bounded by their cumulative costs. For every fixed $c>1$, the least comparison factor $M^*(c,\varepsilon)$ under these assumptions satisfies $\lim_{\varepsilon\downarrow 0}\varepsilon\log M^*(c,\varepsilon)=2$. The guarantee is strictly multiplicative and has no diameter-dependent additive term. Irrevocable metric matching and metrical task systems satisfy the assumptions, and the exponent $2$ is optimal under them.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.08653 — 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-19T09:13:57.842Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).