Cardinality constrained bin-packing problems

We are concerned with a variant of the classical one-dimensional bin-packing problem. n items have to be packed into unit-capacity bins such that the total number of used bins is minimized with the additional constraint that at most k items can be asssigned to one bin. In 1975, Krause et al. analyzed several approximation algorithms for this problem and showed that they all have an asymptotic worst-case performance ratio of 2. No better algorithms have been found so far. We present a new heuristic with an asymptotic worst-case bound of 3/2 and O(n log² n) running time.