News

Colloquia

Bin Packing: From Theory to Experiment and Back Again

Dr. David S. Johnson
AT&T Research

March 18, 2009
Amos Eaton 214, 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.

Abstract:

In the bin classical 1-dimensional packing problem, we are given a list items with sizes between 0 and 1, 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 has been the source of many surprising results about the average case behavior of such algorithms. Many of these surprises were first revealed by experimentation, which led to conjectures and then to proofs. In this talk I will survey these results, and also highlight some as-yet-unproved conjectures suggested by the experimental data.

Bio:

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 in 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. His involvement in experimental analysis of algorithms began in 1983, inspired by his skepticism about the then-new idea of `simulated annealing'. He has taken a lead in encouraging better-quality experimental research, and is the founder and coordinator of the ongoing series of DIMACS Implementation Challenges.

Last updated: Jan. 9, 2009