[Colloquium] TTIC Talks: David Johnson, AT&T Research

[Liv Leader]

When:      Monday, April 2 @ 11 a.m.

Where:     TTIC, 6045 S. Kenwood Avenue, Room 526

Who:        David Johnson, AT&T Research

Title:         Bin Packing: From Theory to Experiment and Back Again

 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.

Host: Yury Makarychev, yury at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120327/e722f926/attachment.htm