Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings

DOI10.1137/S0895480197325936zbMath0951.68192MaRDI QIDQ4490793

Michael R. Garey, David S. Johnson, Edward G. jun. Coffman, Costas Courcoubetis, Peter W. Shor

Publication date: 20 July 2000

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsaverage-case analysisbin packingon-line

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25)

Related Items (8)

Dynamic bin packing of unit fractions items ⋮ Maximizing data locality in distributed systems ⋮ Two-dimensional bin packing with one-dimensional resource augmentation ⋮ Average case analysis of bounded space bin packing algorithms ⋮ On dynamic bin packing: An improved lower bound and resource augmentation analysis ⋮ Bounded-space online bin cover ⋮ Bin packing with directed stackability conflicts ⋮ Adaptive Bin Packing with Overflow

This page was built for publication: Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings