Average-case analysis of the smart next fit algorithm

DOI10.1016/0020-0190(89)90077-XMaRDI QIDQ1120280zbMATH OpenOpenAlexFDO

Authors Prakash V. Ramanan

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90077-x

zbMATH Keywords

approximation algorithmsaverage-case performancebin packingon-line algorithmsworst-case performance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Recommendations

• scientific article; zbMATH DE number 4773
• All-Around Near-Optimal Solutions for the Online Bin Packing Problem
• Average-case analysis of the modified harmonic algorithm
• Average case analysis of bounded space bin packing algorithms
• The average-case analysis of some on-line algorithms for bin packing

Cites work

• A simple on-line bin-packing algorithm
• A stochastic model of bin-packing
• scientific article; zbMATH DE number 4014028 (Why is no real title available?)
• scientific article; zbMATH DE number 3890754 (Why is no real title available?)
• 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-line bin packing in linear time
• Probabilistic analysis for simple one- and two-dimensional bin packing algorithms
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(6)

• Average-case performance analysis of a 2D strip packing algorithm -- NFDH
• Best fit bin packing with random order revisited
• Average case analysis of bounded space bin packing algorithms
• Best fit bin packing with random order revisited
• Near-optimal algorithms for stochastic online bin packing
• Fast algorithms for a large-scale file aggregation problem

This page was built for publication: Average-case analysis of the smart next fit algorithm

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