Metraipolis › archive › dc_6ea567e747ac
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics — arXiv:2611.05769
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05769
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:33.218Z
- SHA-256 of the archived text
7250225c5226e35c1d1360d46df8e88db068242b36581eae54055db327e1e72a- Stable URL of this page
https://metraipolis.com/documento/dc_6ea567e747ac
How to cite
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics — arXiv:2611.05769 — arXiv (en), https://arxiv.org/abs/2611.05769 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6ea567e747ac (Metraipolis archive dc_6ea567e747ac, sha256 7250225c5226e35c1d1360d46df8e88db068242b36581eae54055db327e1e72a)
BibTeX
@misc{dc6ea567e747ac,
title = {Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics — arXiv:2611.05769},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05769},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6ea567e747ac; sha256 7250225c5226e35c1d1360d46df8e88db068242b36581eae54055db327e1e72a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05769. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Online optimization with delays has emerged as a powerful paradigm with numerous applica- tions, including matching, caching, server management, network design, and set cover. In most of these problems, competitive algorithms are known for arbitrary monotone delay functions, even when different requests are associated with different delay functions. The notable exception is online matching with delays, where all previously known algorithms achieving constant or polylogarithmic competitive ratios require the delay functions to be identical, either linear or concave, and known in advance. We study the online minimum-cost perfect matching with delays problem on general metrics. We introduce the broad class of noncrossing delay functions, which strictly generalizes the classic setting of identical concave delay functions while naturally modeling scenarios in which different requests may experience different delay costs. We present the first deterministic $O(1)$-competitive algorithm for the single-location online matching problem with noncrossing delay functions in the non-clairvoyant setting as well as a randomized $O(lognlog\Delta+log^2\Delta)$-competitive algorithm of an arbitrary metric space where $n$ is the number of points of the metric space and $\Delta$ is its aspect ratio. Our result allows each request to have an arbitrary noncrossing delay function, thereby simultaneously removing the assumptions of identical delay functions, concavity, and clairvoyance that were required by all previous constant or polylogarithmic-competitive algorithms. 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.05769 — 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-05T18:21:04.023Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).