On optimal unit fraction bin packing

Abstract. In this paper, we consider a variant of the classical bin packing problem, called unit fraction bin packing (UFBP), where all item sizes are unit fractions. It turns out that the number of bins used by an optimal packing in UFBP is very close to the sum of item sizes. We investigate the relations between these two values, and give a polynomial time optimal algorithm for some cases.