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

Leah Epstein, Lene Monrad Favrholdt

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TidsskriftActa Cybernetica
Vol/bind16
Sider (fra-til)57-66
Antal sider10
ISSN0324-721X
StatusUdgivet - 2003

Fingeraftryk

Competitive Ratio
Bins
Bin Packing Problem
Deterministic Algorithm
Packing
Competitive ratio
Class

Citer dette

@article{ac7f51206fcf11db81a9000ea68e967b,
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 = "2003",
language = "English",
volume = "16",
pages = "57--66",
journal = "Acta Cybernetica",
issn = "0324-721X",
publisher = "Szegedi Tudomanyegyetem",

}

On-Line Maximizing the Number of Items Packed in Variable-Sized Bins. / Epstein, Leah; Favrholdt, Lene Monrad.

I: Acta Cybernetica, Bind 16, 2003, s. 57-66.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

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

AU - Epstein, Leah

AU - Favrholdt, Lene Monrad

PY - 2003

Y1 - 2003

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 - Journal article

VL - 16

SP - 57

EP - 66

JO - Acta Cybernetica

JF - Acta Cybernetica

SN - 0324-721X

ER -