A probabilistic analysis of the next fit decreasing bin packing heuristic

DOI10.1016/0167-6377(86)90013-1zbMath0606.90112OpenAlexW2111869817WikidataQ57401627 ScholiaQ57401627MaRDI QIDQ1085074

J. B. G. Frenk, Alan M. Frieze, Alexander H. G. Rinnooy Kan, János A. Csirik, Gábor Galambos

Publication date: 1986

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

Full work available at URL: http://repub.eur.nl/pub/11645

zbMATH Keywords

probabilistic analysisnext fit decreasing bin packing heuristic

Mathematics Subject Classification ID

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

Related Items

Assigning service requests in voice-over-internet gateway multiprocessors, Probabilistic analysis of the next fit decreasing algorithm for bin- packing, Next-fit packs a list and its reverse into the same number of bins, Expected performance of the shelf heuristic for 2-dimensional packing, Average performance of greedy heuristics for the integer knapsack problem., Average case analysis of bounded space bin packing algorithms, Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem

Cites Work

• Unnamed Item
• A simple on-line bin-packing algorithm
• A stochastic analysis of the NFD bin-packing algorithm
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Martingale Inequalities, Interpolation and NP-Complete Problems
• A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
• Probability Inequalities for Sums of Bounded Random Variables