Batched Bin Packing

Gregory Gutin (gutincs.rhul.ac.uk)
Tommy Jensen (tommycs.rhul.ac.uk)
Anders Yeo (anderscs.rhul.ac.uk)

Abstract: We introduce and study the batched bin packing problem (BBPP), a bin packing problem in which items become available for packing incrementally, one batch at a time. A batched algorithm must pack a batch before the next batch becomes known. A batch may contain several items; the special case when each batch consists of merely one item is the well-studied on-line bin packing problem. We obtain lower bounds for the asymptotic competitive ratio of any algorithm for the BBPP with two batches. We believe that our main lower bound is optimal and provide some support to this conjecture. We suggest studying BBPP and other batched problems.

Keywords: On-line algorithm, lower bounds, bin packing, competitive ratio

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Tech. Report, Royal Holloway, University of London, DCS-TR-04-03, Feb. 2004.

Download: [PDF]

Entry Submitted: 02/09/2004
Entry Accepted: 02/09/2004
Entry Last Modified: 02/13/2004

Modify/Update this entry