Founded in 1966

Distinguished Lecturer Series

34 Years of Bin Packing

David S. Johnson

AT&T Labs

Friday, September 29, 2006
10:30am - SENSQ 5317

Refreshments/meet the speaker at 10:00am

Hosted by Kirk Pruhs

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.

Biography of Speaker

David S. Johnson is Head of the Algorithms and Optimization Department at AT&T Labs-Research in Florham Park, NJ, and has been a researcher at the Labs (in its many incarnations) since 1973, when he received his PhD from MIT. The author of over 100 technical papers, he is perhaps best known as the co-author of COMPUTERS AND INTRACTABILITY: A GUIDE TO THE THEORY OF NP-COMPLETENESS, for which he shared the Lanchester Prize of the Operations Research Society of America (1979). His research interests (in addition to the theory of NP-completeness) include approximation algorithms for combinatorial problems, a subject on which he had several of the first key papers, starting with his PhD thesis on the bin packing problem. Bin packing and its analysis has remained a major interest throughout his career, as he has studied it from many points of view, including worst-case, average-case, and experimental analysis.

You are using an older browser that does not support current Web standards. Although this site is viewable in all browsers, it will look much better in a browser that supports Web standards.