34 Years of Bin Packing
David S. Johnson
AT&T Labs
Friday, September 29, 2006
10:30am - SENSQ 5317
Abstract
In the bin packing problem, one is given a list of 1-dimensional items and asked to pack them into a minimum number of unit-capacity bins. This was one of the first NP-hard problems to be studied from the “approximation algorithm” point of view, and over the years it has served as a laboratory for the study of new questions about approximation algorithms and the development of new techniques for their analysis. In this talk I present a brief survey of this history, covering worst-case, average-case, and experimental results, and leading to the new “sum-of-squares” algorithm for the problem.
