Metraipolis › archive › dc_32b84ba7bd2e

Online Bin Packing with Dispatch Deadlines — arXiv:2611.08792

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.08792
License (as archived)
CC0-1.0
Archived
2026-11-09T22:47:09.663Z
SHA-256 of the archived text
d336f1fce020ac04c3b16c543a0fdefeb2399dbe4b1a624939582f4f42819112
Stable URL of this page
https://metraipolis.com/documento/dc_32b84ba7bd2e

How to cite

Online Bin Packing with Dispatch Deadlines — arXiv:2611.08792 — arXiv (en), https://arxiv.org/abs/2611.08792 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_32b84ba7bd2e (Metraipolis archive dc_32b84ba7bd2e, sha256 d336f1fce020ac04c3b16c543a0fdefeb2399dbe4b1a624939582f4f42819112)
BibTeX
@misc{dc32b84ba7bd2e,
  title = {Online Bin Packing with Dispatch Deadlines — arXiv:2611.08792},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.08792},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_32b84ba7bd2e; sha256 d336f1fce020ac04c3b16c543a0fdefeb2399dbe4b1a624939582f4f42819112},
  year = {2026}
}

Archived text

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

We study a generalization of online bin packing by introducing dispatch deadlines. Items arrive over time in an online fashion. Each item has an arrival time, a size in $(0,1]$, and a deadline, all of which are revealed only when the item arrives. The algorithm must immediately and irrevocably assign the item to a unit-capacity bin that has not yet been dispatched. Each bin must be dispatched no later than the earliest deadline of the items assigned to it, and once it is dispatched, it cannot be used for future items. The goal is to minimize the number of bins used. Applications arise naturally in logistics. Additionally, the offline version of this problem has appeared under several names, including the clique partition problem in weighted interval graphs and the BinSchedule problem. This problem is also a special case of online bin packing with conflicts and is closely related to online bin packing models with delay costs. We study the competitive ratios of several classical online bin packing algorithms when applied to this problem, and show that a similar hierarchy of competitive ratios carries over. Our main technical results are that the competitive ratio of First-Fit is exactly $16/7 \approx 2.28571$, and that no deterministic online algorithm has a competitive ratio less than $11/5 = 2.2$, showing that First-Fit is quite close to best possible. In addition, Next-Fit and Worst-Fit have competitive ratio exactly $3$, and every algorithm in the Any-Fit class has competitive ratio between $16/7$ and $3$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.08792 — 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-11-09T22:40:29.868Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).