Metraipolis › archive › dc_1bb68fb4d6c8
Online Bin Packing with Per-Bin Maximum Delay — arXiv:2609.29589
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.29589
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T07:26:42.026Z
- SHA-256 of the archived text
2c0f6141a7dd568e3b6933674a526227533330a3cc843d0b7e87ff32d6646d97- Stable URL of this page
https://metraipolis.com/documento/dc_1bb68fb4d6c8
How to cite
Online Bin Packing with Per-Bin Maximum Delay — arXiv:2609.29589 — arXiv (en), https://arxiv.org/abs/2609.29589 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1bb68fb4d6c8 (Metraipolis archive dc_1bb68fb4d6c8, sha256 2c0f6141a7dd568e3b6933674a526227533330a3cc843d0b7e87ff32d6646d97)
BibTeX
@misc{dc1bb68fb4d6c8,
title = {Online Bin Packing with Per-Bin Maximum Delay — arXiv:2609.29589},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.29589},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1bb68fb4d6c8; sha256 2c0f6141a7dd568e3b6933674a526227533330a3cc843d0b7e87ff32d6646d97},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29589. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study online bin packing with per-bin maximum delay: each sealed bin incurs a unit opening cost plus the longest waiting time among its items. Offline, this becomes a temporal-span packing objective. We prove strong NP-hardness and rule out absolute approximation factors below three halves unless P equals NP. We complement these barriers with a polynomial constant-factor approximation, exact algorithms for several special cases, and an AFPTAS for the fixed-length weighted endpoint subproblem. For adversarial online inputs, we give an efficient randomized algorithm in the ideal random-real model with expected competitive ratio about 2.418 against an oblivious adversary, together with deterministic and randomized lower bounds. Its analysis couples Next-Fit fragmentation to a negative credit generated by silence clusters. Both frontiers are solved exactly when capacity is nonbinding. We also obtain an exact stochastic benchmark for Poisson arrivals when every item has half the bin capacity: we characterize the offline rate, identify an optimal causal policy, and show that two natural asymptotic ratio notions agree and are bounded by four thirds. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2609.29589 — 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-08T06:44:29.090Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).