Editing Bin packing problem (section)

== Cardinality constraints on the bins ==
There is a variant of bin packing in which there are cardinality constraints on the bins: each bin can contain at most ''k'' items, for some fixed integer ''k''.

* Krause, Shen and Schwetman<ref>{{Cite journal|last1=Krause|first1=K. L.|last2=Shen|first2=V. Y.|last3=Schwetman|first3=H. D.|date=1975-10-01|title=Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems|journal=Journal of the ACM|volume=22|issue=4|pages=522–550|doi=10.1145/321906.321917|s2cid=10214857|issn=0004-5411|doi-access=free}}</ref> introduce this problem as a variant of [[optimal job scheduling]]: a computer has some ''k'' processors. There are some ''n'' jobs that take unit time (1), but have different memory requirements. Each time-unit is considered a single bin. The goal is to use as few bins (=time units) as possible, while ensuring that in each bin, at most ''k'' jobs run. They present several heuristic algorithms that find a solution with at most <math>2 \mathrm{OPT}</math> bins.
* Kellerer and Pferschy<ref>{{Cite journal|last1=Kellerer|first1=H.|last2=Pferschy|first2=U.|date=1999-01-01|title=Cardinality constrained bin-packing problems|url=https://doi.org/10.1023/A:1018947117526|journal=Annals of Operations Research|language=en|volume=92|pages=335–348|doi=10.1023/A:1018947117526|s2cid=28963291|issn=1572-9338}}</ref> present an algorithm with run-time <math>O(n^2 \log{n})</math>, that finds a solution with at most <math>\left\lceil\frac{3}{2}\mathrm{OPT}\right\rceil</math> bins. Their algorithm performs a [[binary search]] for OPT. For every searched value ''m'', it tries to pack the items into 3''m''/2 bins.