Search

In online bin packing problems, items of sizes in [0, 1] are to be partitioned into subsets of total size at most 1, called bins. We introduce a new variant where items are of two types, called black and white, and the item types must alternate in each bin, that is, two items of the same type cannot be assigned consecutively into a bin. This variant generalizes the standard online bin packing problem. We design an online algorithm with an absolute competitive ratio of 3. We further show that a number of well-known algorithms cannot have a better performance, even in the asymptotic sense. Interestingly, we show that this problem is harder than standard online bin packing by proving a general lower bound $1+\frac {1}{2\ln 2}\approx 1.7213$ on the asymptotic competitive ratio of any deterministic or randomized online algorithm. This lower bound exceeds the upper bounds known for the absolute competitive ratio of standard online bin packing. [ABSTRACT FROM AUTHOR]

In the paper we deal with lower bounds constructed for the asymptotic competitive ratio of semi-online bin packing and batched bin packing algorithms.We determine the bounds as the solutions of a related nonlinear optimization problem using theoretical analysis and a reliable numerical global optimization method. Our results improve the lower bounds given in Gutin et al. (Discrete Optim 2:71–82, 2005) for some special cases of the batched bin packing problem. [ABSTRACT FROM AUTHOR]

In 1996 Ivkovič 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. [ABSTRACT FROM AUTHOR]