A Class of Simple Stochastic Online Bin Packing Algorithms

Publikation: Beiträge in ZeitschriftenZeitschriftenaufsätzeForschungbegutachtet

Standard

A Class of Simple Stochastic Online Bin Packing Algorithms. / Hoffmann, Ulrich.
in: Computing, Jahrgang 29, Nr. 3, 01.09.1982, S. 227-239.

Publikation: Beiträge in ZeitschriftenZeitschriftenaufsätzeForschungbegutachtet

Harvard

APA

Vancouver

Hoffmann U. A Class of Simple Stochastic Online Bin Packing Algorithms. Computing. 1982 Sep 1;29(3):227-239. doi: 10.1007/BF02241699

Bibtex

@article{94bf60abbf5d4203a007f6a166d004d0,
title = "A Class of Simple Stochastic Online Bin Packing Algorithms",
abstract = "In the one-dimensional bin packing problem a list of n items has to be packed into a minimum number of unit-capacity bins. A class of linear online algorithms for the approximate solution of bin packing with items drawn from a known probability distribution is presented. Each algorithm depends on the distribution and on a parameter controlling the performance of the algorithm. It is shown that with increasing number of items the expected performance ratio has an arbitrary small deviation from optimum.",
keywords = "Informatics, AMS Subject Classifications: 68C25, approximation algorithms, Bin packing, stochastic algorithms",
author = "Ulrich Hoffmann",
year = "1982",
month = sep,
day = "1",
doi = "10.1007/BF02241699",
language = "English",
volume = "29",
pages = "227--239",
journal = "Computing",
issn = "0010-485X",
publisher = "Springer",
number = "3",

}

RIS

TY - JOUR

T1 - A Class of Simple Stochastic Online Bin Packing Algorithms

AU - Hoffmann, Ulrich

PY - 1982/9/1

Y1 - 1982/9/1

N2 - In the one-dimensional bin packing problem a list of n items has to be packed into a minimum number of unit-capacity bins. A class of linear online algorithms for the approximate solution of bin packing with items drawn from a known probability distribution is presented. Each algorithm depends on the distribution and on a parameter controlling the performance of the algorithm. It is shown that with increasing number of items the expected performance ratio has an arbitrary small deviation from optimum.

AB - In the one-dimensional bin packing problem a list of n items has to be packed into a minimum number of unit-capacity bins. A class of linear online algorithms for the approximate solution of bin packing with items drawn from a known probability distribution is presented. Each algorithm depends on the distribution and on a parameter controlling the performance of the algorithm. It is shown that with increasing number of items the expected performance ratio has an arbitrary small deviation from optimum.

KW - Informatics

KW - AMS Subject Classifications: 68C25

KW - approximation algorithms

KW - Bin packing

KW - stochastic algorithms

UR - http://www.scopus.com/inward/record.url?scp=0020280013&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/b374faad-ba37-35d2-b45b-97e540d7b078/

U2 - 10.1007/BF02241699

DO - 10.1007/BF02241699

M3 - Journal articles

VL - 29

SP - 227

EP - 239

JO - Computing

JF - Computing

SN - 0010-485X

IS - 3

ER -

DOI