Lower bound for the online bin packing problem with restricted repacking
In 1996 Ivkovic and Lloyd [A fundamental restriction on fully dynamic maintenance of bin packing, Inform. Process. Lett., 59 (1996), pp. 229-232] gave the lower bound 4 3 on the asymptotic worst-case ratio for so-called fully dynamic bin packing algorithms, where the number of repackable items in each step is restricted by a constant. In this paper we improve this result to about 1.3871. We present our proof for a semionline case of the classical bin packing, but it works for fully dynamic bin packing as well. We prove the lower bound by analyzing and solving a specific optimization problem. The bound can be expressed exactly using the Lambert W function.
lower bound bin packing semionline algorithm worst-case behavior