Open Collections

Fully Dynamic Bin Packing Revisited

Banff International Research Station for Mathematical Innovation and Discovery

We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is to minimize both the number of bins used as well as the amount of repacking. We measure the repacking by the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. If one wishes to achieve an asymptotic competitive ration of 1 + for the number of bins, a relatively simple argument proves a lower bound of (1=) for the migration factor. We establish a nearly matching upper bound of O((1=)4 log(1=)) using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items n and in 1=. The previous best trade-o was for an asymptotic competitive ratio of 5=4 for the bins (rather than 1 +) and needed an amortized number of O(log n) repackings (while in our scheme the number of repackings is independent of n and non-amortized). Joint work with Klaus Jansen and Kim-Manuel Klein

Mathematics; Computer science; Combinatorics; Theoretical computer science

video/mp4

Author affiliation: Universität zu Lübeck

2016-06-07

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/58241

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/