Next-fit packs a list and its reverse into the same number of bins (Q1109684)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Next-fit packs a list and its reverse into the same number of bins |
scientific article; zbMATH DE number 4070643
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Next-fit packs a list and its reverse into the same number of bins |
scientific article; zbMATH DE number 4070643 |
Statements
Next-fit packs a list and its reverse into the same number of bins (English)
0 references
1988
0 references
Suppose the next-fit algorithm packs \(\{x_ 1,x_ 2,...,x_ n\}\) into k identical bins. Under modest assumptions about what fits into a bin, we prove that next-fit also packs \(\{x_ n,...,x_ 2,x_ 1\}\) into k bins. Thus, the next-fit decreasing algorithm uses the same number of bins as a next-fit increasing algorithm.
0 references
bin-packing
0 references
heuristic
0 references
next-fit decreasing algorithm
0 references
next-fit increasing algorithm
0 references
