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

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