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\)-item bin packing problem is one of the variants introduced by Krause etal. (J ACM 22:522550, 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\). For the online setting of this problem, in which the items are given one by one, Babel etal. (Discret Appl Math 143:238251, 2004) provided lower bounds \(\sqrt{2} \approx 1.41421\) and \(1.5\) on the asymptotic competitive ratio for \(k=2\) and \(3\), respectively. For \(k \ge 4\), some lower bounds (e.g., by van Vliet (Inf Process Lett 43:277284, 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\)-item bin packing problem. First, we improve the previous lower bound \(1.41421\) to \(1.42764\) for \(k=2\). Moreover, we propose a new method to derive lower bounds for general \(k\) and present improved bounds for various cases of \(k \ge 4\). For example, we improve \(1.33333\) to \(1.5\) for \(k = 4\), and \(1.33333\) to \(1.47058\) for \(k = 5\).
bin packing problem cardinality constraint online algorithm competitive analysis