Average case analysis of bounded space bin packing algorithms

DOI10.1007/S00453-007-9073-YMaRDI QIDQ2471807zbMATH OpenOpenAlexFDO

Authors Nir Naaman, Raphael Rom

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)

Recommendations

• Limiting fractal random processes in heavy-tailed systems
• A functional limit theorem for random processes with immigration in the case of heavy tails
• Correlated continuous time random walks
• Fractionally integrated inverse stable subordinators
• Large deviations for subordinated fractional Brownian motion and applications

Cites work

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

Cited in

(12)

• Limiting fractal random processes in heavy-tailed systems
• Average-case analyses of first fit and random fit bin packing
• Average-case analysis of the smart next fit algorithm
• Interior-point-based online stochastic bin packing
• Using Markov chains to design algorithms for bounded-space on-line bin cover
• Fractionally integrated inverse stable subordinators
• Average-case competitive analyses for one-way trading
• Average Case Analysis of Marking Algorithms
• Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison
• Average-Case Competitive Analyses for One-Way Trading
• scientific article; zbMATH DE number 1303568 (Why is no real title available?)
• Theory and Applications of Models of Computation

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

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