Bin Packing: From Theory to Experiment and Back Again
Dr. David S. Johnson
March 18, 2009
Amos Eaton 214, 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.
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.
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.
Hosted by: Dr. Elliot Anshelevich (x6491)
Last updated: Jan. 9, 2009