Average case analysis of bounded space bin packing algorithms

DOI10.1007/s00453-007-9073-yzbMath1203.68310MaRDI QIDQ2471807

Raphael Rom, Nir Naaman

Publication date: 18 February 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9073-y

zbMATH Keywords

Algorithms; Bin packing; Average case analysis; Bounded space; Discrete item size distribution

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

Related Items

Interior-Point-Based Online Stochastic Bin Packing, Average-case competitive analyses for one-way trading, Average-Case Competitive Analyses for One-Way Trading, Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison

Cites Work

• Unnamed Item
• Unnamed Item
• Best \(k\)-fit bin packing
• A probabilistic analysis of the next fit decreasing bin packing heuristic
• Probabilistic analysis of the next fit decreasing algorithm for bin- packing
• Average-case analysis of the smart next fit algorithm
• Fast algorithms for bin packing
• Bin packing with discrete item sizes, part II: Tight bounds on First Fit
• On the sum-of-squares algorithm for bin packing
• Necessary and sufficient conditions for stability of a bin-packing system
• A simple on-line bin-packing algorithm
• A stochastic analysis of the NFD bin-packing algorithm
• Optimal Bin Packing with Items of Random Sizes II
• A stochastic model of bin-packing
• Stochastic analysis of a slotted FIFO communication channel
• Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings
• Markov chains, computer proofs, and average-case analysis of best fit bin packing
• Martingale Inequalities and NP-Complete Problems
• Bounded space on-line bin packing: Best is better than first