Semi-online models for cardinality constrained bin packing
Leah Epstein, Asaf Levin · Journal of Scheduling · 2025
Abstract We study two semi-online models for bin packing and exhibit them on cardinality constrained bin packing with small values of k . In this variant of the bin packing problem, each bin can have at most k items whose total size does not exceed 1. For the semi-online model where the algorithm may use a reordering buffer, we show that even if a single item can be stored in the buffer at any point in time, the best possible asymptotic competitive ratio for the case $$k=2$$ k = 2 is smaller than that of the purely online problem. For the model with two parallel solutions, which is equivalent to the model with advice with a single bit of advice, we show an improved upper bound on the asymptotic competitive ratio for $$k=3$$ k = 3 .