Average case analysis of bounded space bin packing algorithms

DOI10.1007/s00453-007-9073-yzbMath1203.68310OpenAlexW2004367594MaRDI 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

AlgorithmsBin packingAverage case analysisBounded spaceDiscrete item size distribution

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (4)

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 ⋮ Interior-Point-Based Online Stochastic Bin Packing

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

This page was built for publication: Average case analysis of bounded space bin packing algorithms