Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem

J.B.G. Frenk; G. Galambos

Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem

J.B.G. Frenk, G. Galambos

Research output: Book/Report › Report › Academic

451 Downloads (Pure)

Abstract

We present a new approximation algorithm for the two-dimensional bin-packing probIem. The algorithm is based on two one-dimensional bin-packing algorithms. Since the algorithm is of next-fit type it can also be used for those cases where the output is required to be on-line (e.g. if we open a new bin we have no possibility to pack elements into the earlier opened bins). We give a tight bound for its worst-case and show that this bound is a parameter of the maximal sizes of the items to be packed. Moreover, we also present a probabilistic analysis of this algorithm.

Original language	English
Place of Publication	Eindhoven
Publisher	Technische Universiteit Eindhoven
Number of pages	14
Publication status	Published - 1986

Publication series

Name	Memorandum COSOR
Volume	8619
ISSN (Print)	0926-4493

Access to Document

338871Final published version, 3.78 MB

Cite this

@book{916d41d6cc134d92aa0facb45bc1553a,

title = "Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem",

abstract = "We present a new approximation algorithm for the two-dimensional bin-packing probIem. The algorithm is based on two one-dimensional bin-packing algorithms. Since the algorithm is of next-fit type it can also be used for those cases where the output is required to be on-line (e.g. if we open a new bin we have no possibility to pack elements into the earlier opened bins). We give a tight bound for its worst-case and show that this bound is a parameter of the maximal sizes of the items to be packed. Moreover, we also present a probabilistic analysis of this algorithm.",

author = "J.B.G. Frenk and G. Galambos",

year = "1986",

language = "English",

series = "Memorandum COSOR",

publisher = "Technische Universiteit Eindhoven",

}

TY - BOOK

T1 - Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem

AU - Frenk, J.B.G.

AU - Galambos, G.

PY - 1986

Y1 - 1986

N2 - We present a new approximation algorithm for the two-dimensional bin-packing probIem. The algorithm is based on two one-dimensional bin-packing algorithms. Since the algorithm is of next-fit type it can also be used for those cases where the output is required to be on-line (e.g. if we open a new bin we have no possibility to pack elements into the earlier opened bins). We give a tight bound for its worst-case and show that this bound is a parameter of the maximal sizes of the items to be packed. Moreover, we also present a probabilistic analysis of this algorithm.

AB - We present a new approximation algorithm for the two-dimensional bin-packing probIem. The algorithm is based on two one-dimensional bin-packing algorithms. Since the algorithm is of next-fit type it can also be used for those cases where the output is required to be on-line (e.g. if we open a new bin we have no possibility to pack elements into the earlier opened bins). We give a tight bound for its worst-case and show that this bound is a parameter of the maximal sizes of the items to be packed. Moreover, we also present a probabilistic analysis of this algorithm.

M3 - Report

T3 - Memorandum COSOR

BT - Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem

PB - Technische Universiteit Eindhoven

CY - Eindhoven

ER -

Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem

Abstract

Publication series

Access to Document

Fingerprint

Cite this