Metraipolis › archive › dc_6d9dfd5364f0

Online Metric Matching with Unknown i.i.d. Arrivals — arXiv:2611.04275

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04275
License (as archived)
CC0-1.0
Archived
2026-11-04T19:07:27.825Z
SHA-256 of the archived text
61052e1eff6f822ff2082672e49de96fa500296f77d555c6404e2af34be698df
Stable URL of this page
https://metraipolis.com/documento/dc_6d9dfd5364f0

How to cite

Online Metric Matching with Unknown i.i.d. Arrivals — arXiv:2611.04275 — arXiv (en), https://arxiv.org/abs/2611.04275 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6d9dfd5364f0 (Metraipolis archive dc_6d9dfd5364f0, sha256 61052e1eff6f822ff2082672e49de96fa500296f77d555c6404e2af34be698df)
BibTeX
@misc{dc6d9dfd5364f0,
  title = {Online Metric Matching with Unknown i.i.d. Arrivals — arXiv:2611.04275},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04275},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6d9dfd5364f0; sha256 61052e1eff6f822ff2082672e49de96fa500296f77d555c6404e2af34be698df},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04275. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study online metric matching with $n$ servers and $n$ requests drawn independently from an unknown distribution. Each request must be matched immediately and irrevocably to an unused server, and the algorithm receives no samples before the process starts. We give a randomized algorithm that is $O((\log\log\log n)^2)$-competitive on arbitrary metric spaces and $O(1)$-competitive on tree metrics. These guarantees match the corresponding bounds for known i.i.d. request distributions in [GGPW19] up to constant factors. More generally, our competitive ratio is $O(\alpha(n))$ whenever the Fair-Bias algorithm introduced in that work has competitive ratio $\alpha(n)$ for known i.i.d. arrivals on the same class of metrics. Consequently, proving that Fair-Bias is constant-competitive on general metrics would also yield a constant-competitive algorithm for unknown i.i.d. arrivals.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.04275 — 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-11-04T18:40:52.430Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).