Metraipolis › archive › dc_1985fa86a837

Metric Facility Location under Batched Random Order — arXiv:2611.04920

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04920
License (as archived)
CC0-1.0
Archived
2026-11-04T12:59:22.924Z
SHA-256 of the archived text
61c058c9b7be307f25fb0212554d81909b390f3c2566c9ca0cb99e62834b173c
Stable URL of this page
https://metraipolis.com/documento/dc_1985fa86a837

How to cite

Metric Facility Location under Batched Random Order — arXiv:2611.04920 — arXiv (en), https://arxiv.org/abs/2611.04920 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1985fa86a837 (Metraipolis archive dc_1985fa86a837, sha256 61c058c9b7be307f25fb0212554d81909b390f3c2566c9ca0cb99e62834b173c)
BibTeX
@misc{dc1985fa86a837,
  title = {Metric Facility Location under Batched Random Order — arXiv:2611.04920},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04920},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1985fa86a837; sha256 61c058c9b7be307f25fb0212554d81909b390f3c2566c9ca0cb99e62834b173c},
  year = {2026}
}

Archived text

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

We study online metric facility location in the batched random-order model. An adversary partitions $n$ clients into $B$ nonempty batches, which arrive in uniformly random order. Each batch is revealed in full, and its clients must be connected to open facilities before the next batch arrives. Openings and assignments are irrevocable, and the objective is to minimize the total opening and connection cost. For both uniform and nonuniform opening costs, we prove that the tight competitive ratio is \[ \Theta\!\left(\min\left\{\log(B+1), \sqrt{\log(n-B+2)}\right\}\right). \] Thus, the ratio is constant both when there is a single batch and when every batch is a singleton, but intermediate numbers of batches can require a $\Theta(\sqrt{\log n})$ ratio. Our algorithms build on Meyerson's algorithm (2001) and do not need to know $n$ nor $B$. A key algorithmic novelty is that we process the clients in a batch one by one in uniform random order (hence neglecting the global properties of the batch). We present a novel analysis of this algorithm that hinges on the random order of the batches, as well as of the clients within each batch. We also provide a matching competitive ratio lower bound already for uniform costs, and even when the entire metric is known in advance.

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.04920 — 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-04T12:35:02.325Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).