Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem (Q580978)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4018385
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem |
scientific article; zbMATH DE number 4018385 |
Statements
Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem (English)
0 references
1987
0 references
We present a new approximation algorithm for the two-dimensional bin- packing problem. The algorithm is based on two one-dimensional bin- packing algorithms. Since the algorithm is of next-fit type it can also used for those cases where the output is required to be on-line (e.g. if we open an 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.
0 references
two-dimensional packing
0 references
bin-packing
0 references
heuristic algorithm
0 references
worst-case analysis
0 references
probabilistic analysis
0 references
on-line algorithm
0 references
0.8453271389007568
0 references
0.8392249941825867
0 references
0.83919358253479
0 references
0.8376352787017822
0 references
