Metraipolis › archive › dc_d1f44ee013e8

Pure Tail Constraints for Online Problems — arXiv:2609.35337

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.35337
License (as archived)
CC0-1.0
Archived
2026-10-08T00:19:02.871Z
SHA-256 of the archived text
e24dd6f31dfd8dfcdb8ace9dda2a37bd36f2b7624c1693e3b85683adf362ab58
Stable URL of this page
https://metraipolis.com/documento/dc_d1f44ee013e8

How to cite

Pure Tail Constraints for Online Problems — arXiv:2609.35337 — arXiv (en), https://arxiv.org/abs/2609.35337 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d1f44ee013e8 (Metraipolis archive dc_d1f44ee013e8, sha256 e24dd6f31dfd8dfcdb8ace9dda2a37bd36f2b7624c1693e3b85683adf362ab58)
BibTeX
@misc{dcd1f44ee013e8,
  title = {Pure Tail Constraints for Online Problems — arXiv:2609.35337},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.35337},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d1f44ee013e8; sha256 e24dd6f31dfd8dfcdb8ace9dda2a37bd36f2b7624c1693e3b85683adf362ab58},
  year = {2026}
}

Archived text

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

Controlling tail risk is an important objective in online optimization, and recently it has been studied in the context of competitive analysis. Continuing this line of research, we investigate pure tail constraints, which capture the tradeoff between expected and worst-case competitiveness. For two fundamental search problems, online bidding and line search, we derive the Pareto-optimal frontiers of this tradeoff. We then investigate another classic problem, TCP acknowledgment, which has structure similar to the iterated ski rental problem. There, we construct an algorithm whose tradeoff coincides with the known Pareto-optimal tradeoff for ski rental. The lower bounds for this problem are substantially more involved as the problem exhibits adaptive structure: an online algorithm observes requests of the adversary (packet arrivals) and may adaptively adjust its actions (acknowledgments) on this basis. We emphasize that all previous work on tail risk in the context of competitive analysis was restricted to non-adaptive problems, where the feedback given to an algorithm was essentially limited to a binary indicator of whether the algorithm has succeeded or not. Nonetheless, we identify a set of constraints implied by tail bounds in this adaptive setting, and show that they imply a nontrivial lower bound on the TCP acknowledgment 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.35337 — 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.779Z 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).