We consider a variation of the bin packing problem in which a fixed number of bins can be filled to a level exceeding 1. The goal is to minimize the total cost of the bins used, where the cost of a bin filled to level L is defined to be max(1,L). We discuss approximation algorithms for this problem.
(Joint work with Ed Coffman.)