Metraipolis › archive › dc_9b454b414fdf

A Deterministic O(log m)-Competitive Algorithm for Online Minimum Cost Bipartite Matching with Delays — arXiv:2611.01553

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.01553
License (as archived)
CC0-1.0
Archived
2026-11-03T18:58:54.212Z
SHA-256 of the archived text
7a2b10f20fb4d40d9f51d18c6b2dd1d035552ef20add0db01588a2337b51f8de
Stable URL of this page
https://metraipolis.com/documento/dc_9b454b414fdf

How to cite

A Deterministic O(log m)-Competitive Algorithm for Online Minimum Cost Bipartite Matching with Delays — arXiv:2611.01553 — arXiv (en), https://arxiv.org/abs/2611.01553 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9b454b414fdf (Metraipolis archive dc_9b454b414fdf, sha256 7a2b10f20fb4d40d9f51d18c6b2dd1d035552ef20add0db01588a2337b51f8de)
BibTeX
@misc{dc9b454b414fdf,
  title = {A Deterministic O(log m)-Competitive Algorithm for Online Minimum Cost Bipartite Matching with Delays — arXiv:2611.01553},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.01553},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9b454b414fdf; sha256 7a2b10f20fb4d40d9f51d18c6b2dd1d035552ef20add0db01588a2337b51f8de},
  year = {2026}
}

Archived text

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

In the online Minimum cost Bipartite Perfect Matching with Delays (MBPMD) problem, $m$ requests and $m$ servers arrive over time in a metric space. An online algorithm has to match each request to a server and can postpone a matching decision by paying the delay cost. The objective is to minimize the total distance and delay cost. Azar, Chiplunkar, and Kaplan gave a randomized $O(\log n)$-competitive algorithm for metric spaces with $n$ points that are known in advance. For deterministic algorithms, however, the best known competitive ratio in general metric spaces was $O(m^{0.59})$, due to Azar and Jacob-Fanani. On the line, Kuo proposed the Virtual Robust Matching (VRM) algorithm and showed that it is $O(\sqrt{m}\log^2 m)$-competitive. We prove that VRM is $O(\log m)$-competitive for the MBPMD problem in any metric space. VRM is deterministic and does not need to know the metric space or $m$ in advance. It is the first deterministic polylogarithmic-competitive algorithm for the MBPMD problem in general metric spaces. Unlike the previous analysis of VRM, our analysis does not rely on a geometric decomposition of the metric space. Instead, it charges the waiting time of requests over time to the edges of a fixed optimal matching. We also extend VRM to the non-bipartite version and prove that the resulting deterministic algorithm is $O(\log m)$-competitive. This improves the $O(\log^5 m)$ bound of Dufay and Wattenhofer and matches a concurrent result of Ahmadian, Chawla, Kumar, Purohit, and Zhang. The proof that VRM is $O(\log m)$-competitive and its non-bipartite extension were found by GPT-6 Astra (OpenAI) with almost no human input. We used Claude Opus 5.5 (Anthropic) to simplify and present the results. See the AI Usage and Methodology section for details. We take full responsibility for this paper.

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.01553 — 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-03T18:18:07.717Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).