Tight Bounds for Dynamic Bin Packing with Predictions
A variant of the Dynamic Bin Packing (DBP) problem known as MinUsageTime DBP seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This paper studies MinUsageTime DBP with predictions about item durations and establishes tight competitiveness bounds over the entire spectrum of prediction errors.
Authors
- Xueyan Tang (ORCID: https://orcid.org/0000-0002-7404-7595)
- Mozhengfu Liu (ORCID: https://orcid.org/0000-0001-6181-9958)
Institutions
- Northwestern University (US)
- Nanyang Technological University (SG)
Publication Details
- Journal
- ACM SIGMETRICS Performance Evaluation Review
- Published
- 2025-06-16
- DOI
- https://doi.org/10.1145/3744970.3727322
- Citations
- 1
- Primary Topic
- Optimization and Packing Problems
- Type
- article
- Field-Weighted Citation Impact
- 1.24
Funders
- Ministry of Education - Singapore