## 17 March 2000:

Packing Stretchable Bins

George Lueker, ICS, UC Irvine

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.)