2017/11/03 by Björn Feldkord, Feldkord, Björn, Matthias Feldotto +3 · 1 citation
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1711.01231
openalex publication_date 2017/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a variant of the classical Bin Packing Problem, called Fully Dynamic Bin Packing. In this variant, items of a size in (0,1] must be packed in bins of unit size. In each time step, an item either arrives or departs from the packing. An algorithm for this problem must maintain a feasible packing while only repacking a bounded number of items in each time step. We develop an algorithm which repacks only a constant number of items per time step and, unlike previous work, does not rely on bundling of small items which allowed those solutions to move an unbounded number of small items as one. Our algorithm has an asymptotic approximation ratio of roughly 1.3871 which is complemented by a lower bound of Balogh et al., resulting in a tight approximation ratio for this problem. As a direct corollary, we also close the gap to the lower bound of the Relaxed Online Bin Packing Problem in which only insertions of items occur.