Metraipolis › archive › dc_466bbfbee16e

Online Allocation using Few Samples — arXiv:2609.17343

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.17343
License (as archived)
CC0-1.0
Archived
2026-10-15T19:31:08.804Z
SHA-256 of the archived text
0898fb326f6769ed6796ac7a170db46625c0b805d8ce3919cb2487f1f7ac4010
Stable URL of this page
https://metraipolis.com/documento/dc_466bbfbee16e

How to cite

Online Allocation using Few Samples — arXiv:2609.17343 — arXiv (en), https://arxiv.org/abs/2609.17343 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_466bbfbee16e (Metraipolis archive dc_466bbfbee16e, sha256 0898fb326f6769ed6796ac7a170db46625c0b805d8ce3919cb2487f1f7ac4010)
BibTeX
@misc{dc466bbfbee16e,
  title = {Online Allocation using Few Samples — arXiv:2609.17343},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.17343},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_466bbfbee16e; sha256 0898fb326f6769ed6796ac7a170db46625c0b805d8ce3919cb2487f1f7ac4010},
  year = {2026}
}

Archived text

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

We study online allocation problems where $n$ requests over $m$ resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures both Online Resource Allocation, where the goal is to maximize value subject to resource budgets, and Online Load Balancing, where the goal is to minimize the makespan. We seek $(1\pm\epsilon)$-competitive algorithms in the large-budget or large-makespan regime. We consider a sampling model that generalizes the following two well-studied sampling models. In the Single-Sample Prophet Inequality ($\mathsf{SSPI}$) model, request $t$ is drawn from an unknown distribution $\mathcal{D}_t$, and the algorithm is given one independent sample from each $\mathcal{D}_t$ before the online phase. In the $p$-$\mathsf{Sample}$ model, the requests are adversarial, but a uniformly random $p$-fraction is revealed upfront as training data. Although near-optimal algorithms are known in the easier random-order model ($\mathsf{RO}$), where the requests arrive in a uniformly random order, prior algorithms for $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$ were problem-specific and incurred substantially worse dependencies on $\epsilon$, $m$, and $n$. Our main contribution is a general framework that converts $\mathsf{RO}$ algorithms into algorithms for the $p$-$\mathsf{Preview}$ model, a model that generalizes both $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$. As consequences, we obtain near-optimal bounds for Online Resource Allocation, generalized Online Load Balancing, and online mixed packing-covering problems in these adversarial-order sampling models, significantly improving the bounds of [Ghuge, Singla, Wang (STOC'25)] and [Gupta and Molinaro (SODA'26)].

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-16 in cs.GT).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.17343 — 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-15T18:39:23.386Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).