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

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Annual International Conference on Computing and Combinatorics
Antal sider	12
Forlag	Springer Science+Business Media
Publikationsdato	2002
Sider	467-476
ISBN (Trykt)	3-540-43996-X
Status	Udgivet - 2002
Begivenhed	Annual International Conference on Computing and Combinatorics - Singapore, Singapore Varighed: 24. aug. 2010 → … Konferencens nummer: 8

Konference

Konference	Annual International Conference on Computing and Combinatorics
Nummer	8
Land/Område	Singapore
By	Singapore
Periode	24/08/2010 → …

Citationsformater

@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

Konference

Fingeraftryk

Citationsformater