A Simple On-Line Bin-Packing Algorithm

C. C. Lee; D. T. Lee

doi:10.1145/3828.3833

A Simple On-Line Bin-Packing Algorithm

C. C. Lee^*, D. T. Lee

^*Corresponding author for this work

Electrical and Computer Engineering

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

252 Scopus citations

Abstract

The one-dimensional on-line bin-packing problem is considered, A simple O(1)-space and O(n)-time algorithm, called HARMONIC_M, is presented. It is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the O(n)-space and O(n log n)-time algorithm FIRST FIT. Also shown is that 1.691 … is a lower bound for all 0(1)-space on-line bin-packing algorithms. Finally a revised version of HARMONIC_M, an O(n)-space and O(n)- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636.d.

Original language	English (US)
Pages (from-to)	562-572
Number of pages	11
Journal	Journal of the ACM (JACM)
Volume	32
Issue number	3
DOIs	https://doi.org/10.1145/3828.3833
State	Published - Jul 1 1985

ASJC Scopus subject areas

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Access to Document

10.1145/3828.3833

Fingerprint Dive into the research topics of 'A Simple On-Line Bin-Packing Algorithm'. Together they form a unique fingerprint.

Cite this

@article{6d84747797a94f3492fed3737d81c0a9,

title = "A Simple On-Line Bin-Packing Algorithm",

abstract = "The one-dimensional on-line bin-packing problem is considered, A simple O(1)-space and O(n)-time algorithm, called HARMONICM, is presented. It is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the O(n)-space and O(n log n)-time algorithm FIRST FIT. Also shown is that 1.691 … is a lower bound for all 0(1)-space on-line bin-packing algorithms. Finally a revised version of HARMONICM, an O(n)-space and O(n)- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636.d.",

author = "Lee, {C. C.} and Lee, {D. T.}",

year = "1985",

month = jul,

day = "1",

doi = "10.1145/3828.3833",

language = "English (US)",

volume = "32",

pages = "562--572",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "3",

}

TY - JOUR

T1 - A Simple On-Line Bin-Packing Algorithm

AU - Lee, C. C.

AU - Lee, D. T.

PY - 1985/7/1

Y1 - 1985/7/1

N2 - The one-dimensional on-line bin-packing problem is considered, A simple O(1)-space and O(n)-time algorithm, called HARMONICM, is presented. It is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the O(n)-space and O(n log n)-time algorithm FIRST FIT. Also shown is that 1.691 … is a lower bound for all 0(1)-space on-line bin-packing algorithms. Finally a revised version of HARMONICM, an O(n)-space and O(n)- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636.d.

AB - The one-dimensional on-line bin-packing problem is considered, A simple O(1)-space and O(n)-time algorithm, called HARMONICM, is presented. It is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the O(n)-space and O(n log n)-time algorithm FIRST FIT. Also shown is that 1.691 … is a lower bound for all 0(1)-space on-line bin-packing algorithms. Finally a revised version of HARMONICM, an O(n)-space and O(n)- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636.d.

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

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

U2 - 10.1145/3828.3833

DO - 10.1145/3828.3833

M3 - Article

AN - SCOPUS:0022093691

VL - 32

SP - 562

EP - 572

JO - Journal of the ACM

JF - Journal of the ACM

SN - 0004-5411

IS - 3

ER -