Improved lower bounds for the online bin packing problem with cardinality constraints

The bin packing problem has been extensively studied and numerous variants have been considered. The $$k$$ k -item bin packing problem is one of the variants introduced by Krause et al. (J ACM 22:522–550, 1975). In addition to the formulation of the classical bin packing problem, this problem imposes a cardinality constraint that the number of items packed into each bin must be at most $$k$$ k . For the online setting of this problem, in which the items are given one by one, Babel et al. (Discret Appl Math 143:238–251, 2004) provided lower bounds $$\sqrt{2} \approx 1.41421$$ 2 ≈ 1.41421 and $$1.5$$ 1.5 on the asymptotic competitive ratio for $$k=2$$ k = 2 and $$3$$ 3 , respectively. For $$k \ge 4$$ k ≥ 4 , some lower bounds (e.g., by van Vliet (Inf Process Lett 43:277–284, 1992) for the online bin packing problem, i.e., a problem without cardinality constraints, can be applied to this problem. In this paper we consider the online $$k$$ k -item bin packing problem. First, we improve the previous lower bound $$1.41421$$ 1.41421 to $$1.42764$$ 1.42764 for $$k=2$$ k = 2 . Moreover, we propose a new method to derive lower bounds for general $$k$$ k and present improved bounds for various cases of $$k \ge 4$$ k ≥ 4 . For example, we improve $$1.33333$$ 1.33333 to $$1.5$$ 1.5 for $$k = 4$$ k = 4 , and $$1.33333$$ 1.33333 to $$1.47058$$ 1.47058 for $$k = 5$$ k = 5 .