Batched bin packing

Gregory Gutin; Tommy Jensen; Anders Yeo

doi:10.1016/j.disopt.2004.11.001

Batched bin packing

Gregory Gutin
, Tommy Jensen
, Anders Yeo

Royal Holloway University of London

Research output: Contribution to journal › Article › peer-review

27 Citations (Scopus)

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.

Original language	English
Pages (from-to)	71-82
Number of pages	12
Journal	Discrete Optimization
Volume	2
Issue number	1
DOIs	https://doi.org/10.1016/j.disopt.2004.11.001
Publication status	Published - 30 Mar 2005
Externally published	Yes

Keywords

Bin packing
Competitive ratio
Lower bounds
On-line algorithm

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.disopt.2004.11.001

Cite this

@article{864a097dfaa9402f8761d5c0667d4ac9,

title = "Batched bin packing",

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 = "Bin packing, Competitive ratio, Lower bounds, On-line algorithm",

author = "Gregory Gutin and Tommy Jensen and Anders Yeo",

year = "2005",

month = mar,

day = "30",

doi = "10.1016/j.disopt.2004.11.001",

language = "English",

volume = "2",

pages = "71--82",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Batched bin packing

AU - Gutin, Gregory

AU - Jensen, Tommy

AU - Yeo, Anders

PY - 2005/3/30

Y1 - 2005/3/30

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

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

KW - Bin packing

KW - Competitive ratio

KW - Lower bounds

KW - On-line algorithm

UR - https://www.scopus.com/pages/publications/14844344067

U2 - 10.1016/j.disopt.2004.11.001

DO - 10.1016/j.disopt.2004.11.001

M3 - Article

AN - SCOPUS:14844344067

SN - 1572-5286

VL - 2

SP - 71

EP - 82

JO - Discrete Optimization

JF - Discrete Optimization

IS - 1

ER -

Batched bin packing

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this