On-Line Maximizing the Number of Items Packed in Variable-Sized Bins

Leah Epstein; Lene Monrad Favrholdt

On-Line Maximizing the Number of Items Packed in Variable-Sized Bins

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

We study an on-line bin packing problem. A fixed number n of bins, possibly of different sizes, are given. The items arrive on-line, and the goal is to pack as many items as possible. It is known that there exists a legal packing of the whole sequence in the n bins. We consider fair algorithms that reject an item, only if it does not fit in the empty space of any bin. We show that the competitive ratio of any fair, deterministic algorithm lies between 1/2 and 2/3, and that a class of algorithms including Best-Fit has a competitive ratio of exactly n/2n−1.

Original language	English
Title of host publication	Annual International Conference on Computing and Combinatorics
Number of pages	12
Publisher	Springer Science+Business Media
Publication date	2002
Pages	467-476
ISBN (Print)	3-540-43996-X
Publication status	Published - 2002
Event	Annual International Conference on Computing and Combinatorics - Singapore, Singapore Duration: 24. Aug 2010 → … Conference number: 8

Conference

Conference	Annual International Conference on Computing and Combinatorics
Number	8
Country/Territory	Singapore
City	Singapore
Period	24/08/2010 → …

Cite this

@inproceedings{1c842cc062e511ddb1a1000ea68e967b,

title = "On-Line Maximizing the Number of Items Packed in Variable-Sized Bins",

abstract = "We study an on-line bin packing problem. A fixed number n of bins, possibly of different sizes, are given. The items arrive on-line, and the goal is to pack as many items as possible. It is known that there exists a legal packing of the whole sequence in the n bins. We consider fair algorithms that reject an item, only if it does not fit in the empty space of any bin. We show that the competitive ratio of any fair, deterministic algorithm lies between 1/2 and 2/3, and that a class of algorithms including Best-Fit has a competitive ratio of exactly n/2n−1.",

author = "Leah Epstein and Favrholdt, {Lene Monrad}",

year = "2002",

language = "English",

isbn = "3-540-43996-X",

pages = "467--476",

booktitle = "Annual International Conference on Computing and Combinatorics",

publisher = "Springer Science+Business Media",

address = "United States",

note = "Annual International Conference on Computing and Combinatorics ; Conference date: 24-08-2010",

}

TY - GEN

T1 - On-Line Maximizing the Number of Items Packed in Variable-Sized Bins

AU - Epstein, Leah

AU - Favrholdt, Lene Monrad

N1 - Conference code: 8

PY - 2002

Y1 - 2002

N2 - We study an on-line bin packing problem. A fixed number n of bins, possibly of different sizes, are given. The items arrive on-line, and the goal is to pack as many items as possible. It is known that there exists a legal packing of the whole sequence in the n bins. We consider fair algorithms that reject an item, only if it does not fit in the empty space of any bin. We show that the competitive ratio of any fair, deterministic algorithm lies between 1/2 and 2/3, and that a class of algorithms including Best-Fit has a competitive ratio of exactly n/2n−1.

AB - We study an on-line bin packing problem. A fixed number n of bins, possibly of different sizes, are given. The items arrive on-line, and the goal is to pack as many items as possible. It is known that there exists a legal packing of the whole sequence in the n bins. We consider fair algorithms that reject an item, only if it does not fit in the empty space of any bin. We show that the competitive ratio of any fair, deterministic algorithm lies between 1/2 and 2/3, and that a class of algorithms including Best-Fit has a competitive ratio of exactly n/2n−1.

M3 - Article in proceedings

SN - 3-540-43996-X

SP - 467

EP - 476

BT - Annual International Conference on Computing and Combinatorics

PB - Springer Science+Business Media

T2 - Annual International Conference on Computing and Combinatorics

Y2 - 24 August 2010

ER -

On-Line Maximizing the Number of Items Packed in Variable-Sized Bins

Abstract

Conference

Fingerprint

Cite this