ICS Theory Group

ICS 269, Winter 2000: Theory Seminar

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