Metraipolis › archive › dc_ce8d981952ff

Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness — arXiv:2609.21889

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.21889
License (as archived)
CC0-1.0
Archived
2026-10-10T02:46:05.479Z
SHA-256 of the archived text
9e61f41d66d6e9add771cfeb923dd3643b04aeeda655a420493ac16af0da4a02
Stable URL of this page
https://metraipolis.com/documento/dc_ce8d981952ff

How to cite

Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness — arXiv:2609.21889 — arXiv (en), https://arxiv.org/abs/2609.21889 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ce8d981952ff (Metraipolis archive dc_ce8d981952ff, sha256 9e61f41d66d6e9add771cfeb923dd3643b04aeeda655a420493ac16af0da4a02)
BibTeX
@misc{dcce8d981952ff,
  title = {Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness — arXiv:2609.21889},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.21889},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ce8d981952ff; sha256 9e61f41d66d6e9add771cfeb923dd3643b04aeeda655a420493ac16af0da4a02},
  year = {2026}
}

Archived text

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

Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study this online algorithms with a sample (OAS) model. We show a tight $O\left(\log (1/p) \cdot \log m + \log n\right)$-competitive algorithm for set cover, exponentially improving upon the $O\left(1/p \cdot \log (mn)\right)$ guarantee of Gupta et al. (SODA'24) and answering an open question therein. Our techniques extend to covering integer programs and non-metric facility location, also yielding tight bounds for these problems. Further, we give an $O(\log (1/p)/ \log \log (1/p))$-competitive algorithm for metric facility location, answering an open question of Argue et al. (NeurIPS'22). We then introduce and study the robust variant of the OAS model, in which an adversary is allowed to arbitrarily modify $k$ elements of the $p$-sample. For set cover, covering integer programs, and non-metric facility location, we obtain a tight competitive ratio of $O\left(\log (k/p) \cdot \log m + \log n\right)$. For metric facility location and Steiner tree, we obtain tight competitive ratios of $O\left(\log (k/p) / \log \log (k/p) \right)$ and $O\left(\log (k/p)\right)$ respectively. To the best of our knowledge, these are the first results for robust algorithms in the OAS setting.

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