Tight Bounds for Dynamic Bin Packing with Predictions
Open Access
- 16 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 53 (1) , 94-96
Abstract
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.Keywords
Funding Information
- Ministry of Education, Singapore (MOE-T2EP20122-0007)
This publication has 6 references indexed in Scilit:
- Dynamic Bin Packing with PredictionsProceedings of the ACM on Measurement and Analysis of Computing Systems, 2022
- Tight Bounds for Clairvoyant Dynamic Bin PackingACM Transactions on Parallel Computing, 2019
- Tight Bounds for Clairvoyant Dynamic Bin Packing2017
- Competitiveness of Dynamic Bin Packing for Online Cloud Server AllocationIEEE/ACM Transactions on Networking, 2016
- Dynamic Bin Packing for On-Demand Cloud Resource AllocationIEEE Transactions on Parallel and Distributed Systems, 2015
- On dynamic bin packing for resource allocation in the cloud2014