 |
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, highlighting the many surprising average case behavior results that have been obtained. Several of these surprises were first revealed by experimentation, which led to conjectures and then to proofs, and I will describe this interplay between experimentation and theory. I'll also highlight some as-yet-unproven conjectures suggested by the experimental data.
This talk will be accessible to undergraduates.
|