Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing

DOI10.1137/S0036144501395423zbMath0999.68260MaRDI QIDQ2780629

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

Publication date: 15 April 2002

Published in: SIAM Review (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsaverage-case analysisonlinebin packing

Mathematics Subject Classification ID

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

Related Items

On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem