Probabilistic analysis of the next fit decreasing algorithm for bin- packing

DOI10.1016/0167-6377(87)90018-6zbMath0628.90059OpenAlexW2072813799MaRDI QIDQ1093532

WanSoo T. Rhee

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0167-6377(87)90018-6

zbMATH Keywords

bin-packingdeterministic inequalityprobabilistic analysis of next fit decreasing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27)

Related Items (2)

Next-fit packs a list and its reverse into the same number of bins ⋮ Average case analysis of bounded space bin packing algorithms

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
• Probability Inequalities for Sums of Bounded Random Variables

This page was built for publication: Probabilistic analysis of the next fit decreasing algorithm for bin- packing