Next-fit packs a list and its reverse into the same number of bins

DOI10.1016/0167-6377(88)90060-0MaRDI QIDQ1109684zbMATH OpenOpenAlexFDO

Authors David C. Fisher

Publication date 1988

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(88)90060-0

zbMATH Keywords

bin-packingheuristicnext-fit decreasing algorithmnext-fit increasing algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27)

Review text

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.

Recommendations

• Tight Worst-Case Performance Bounds for Next-k-Fit Bin Packing
• Best k-fit bin packing
• Algorithm NextFit for the bin packing problem
• scientific article; zbMATH DE number 4050974
• Publication:4205077

Cites work

• A probabilistic analysis of the next fit decreasing bin packing heuristic
• A stochastic analysis of the NFD bin-packing algorithm
• A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
• scientific article; zbMATH DE number 4033058 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On Packing Two-Dimensional Bins
• Probabilistic analysis of the next fit decreasing algorithm for bin- packing

Cited in

(4)

• More on batched bin packing
• Quality of strong equilibria for selfish bin packing with uniform cost sharing
• A note on a selfish bin packing problem
• On-line bin packing ? A restricted survey

This page was built for publication: Next-fit packs a list and its reverse into the same number of bins

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109684)