Metraipolis › archive › dc_ccfca028d42e

Online Covering with Maximum Delay under Subadditive Service Costs — arXiv:2609.32675

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.32675
License (as archived): CC0-1.0
Archived: 2026-10-08T00:18:55.046Z
SHA-256 of the archived text: 06bdd5e457ddd1714d72f23dbbae356d6eb40c843b80de04b34450b4fddd4cd9
Stable URL of this page: https://metraipolis.com/documento/dc_ccfca028d42e

How to cite

Online Covering with Maximum Delay under Subadditive Service Costs — arXiv:2609.32675 — arXiv (en), https://arxiv.org/abs/2609.32675 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ccfca028d42e (Metraipolis archive dc_ccfca028d42e, sha256 06bdd5e457ddd1714d72f23dbbae356d6eb40c843b80de04b34450b4fddd4cd9)

BibTeX

@misc{dcccfca028d42e,
  title = {Online Covering with Maximum Delay under Subadditive Service Costs — arXiv:2609.32675},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.32675},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ccfca028d42e; sha256 06bdd5e457ddd1714d72f23dbbae356d6eb40c843b80de04b34450b4fddd4cd9},
  year = {2026}
}

Archived text

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

We study online covering in which each instantaneous service pays its purchase cost and one maximum waiting time, with no effect on future requests. For static realizable services, monotone subadditivity suffices for optimal competitive ratios; submodularity is unnecessary. A normalized monotone subadditive lower-bound oracle with realization factor $\rho$ yields ratios $\rho+1$ deterministically and $1/(1-e^{-1/\rho})$ randomly against an oblivious adversary. Exact batch optimization gives the optimal constants $2$ and $e/(e-1)$. The randomized algorithm uses one global threshold on a seed-independent virtual-height trajectory, whose active time is a lower bound on the offline optimum. Weighted vertex cover gives a strict separation from submodularity on a three-edge bipartite path, with polynomial-time batch implementations through min-cut and LP rounding. An offline consecutive-batch normal form also transfers static approximation guarantees to the offline problem.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.32675 — 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-07T23:56:21.757Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).