Probabilistic analysis for simple one- and two-dimensional bin packing algorithms

DOI10.1016/0020-0190(80)90041-1zbMath0453.68014OpenAlexW1981738785MaRDI QIDQ1149248

Greg N. Frederickson

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1016/0020-0190(80)90041-1

zbMATH Keywords

approximation algorithmNP-complete problemexpected performance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Related Items (15)

A 71/60 theorem for bin packing ⋮ Bin packing as a random walk: A note on Knödel's paper ⋮ The nesting problem in the leather manufacturing industry ⋮ The average-case analysis of some on-line algorithms for bin packing ⋮ FFD bin packing for item sizes with uniform distributions on \([0,\frac12\).] ⋮ Packing items from a triangular distribution ⋮ Average-case analysis of the smart next fit algorithm ⋮ Efficiency of two classes of dynamic scheduling algorithms in multiprocessor computer systems ⋮ Expected performance of the shelf heuristic for 2-dimensional packing ⋮ A class of simple stochastic online bin packing algorithms ⋮ A two-phase heuristic for strip packing: Algorithm and probabilistic analysis ⋮ Heuristic methods and applications: A categorized survey ⋮ Average-case analysis of the modified harmonic algorithm ⋮ Probabilistic behaviour of optimal bin-packing solutions ⋮ An O(n) bin-packing algorithm for uniformly distributed data

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast algorithms for bin packing
• New Algorithms for Bin Packing
• Two-dimensional packing: expected performance of simple level algorithms
• A stochastic model of bin-packing
• Orthogonal Packings in Two Dimensions
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

This page was built for publication: Probabilistic analysis for simple one- and two-dimensional bin packing algorithms