STORY%MIT-MC@sri-unix.UUCP (02/17/84)
From: Kenneth Byrd Story <STORY @ MIT-MC>
[Forwarded from the MIT-MC bboard by Laws@SRI-AI.]
TITLE: "The Computational Discovery of Mathematical Laws: Experiments in Bin
Packing"
SPEAKER: Dr. Jon Bentley, Bell Laboratories, Murray Hill
DATE: Wednesday, February 22, 1984
TIME: 3:30pm Refreshments
4:15pm Lecture
PLACE: Bldg. 2-338
Bin packing is a typical NP-complete problem that arises in many applications.
This talk describes experiments on two simple bin packing heuristics (First Fit
and First Fit Decreasing) which show that they perform extremely well on
randomly generated data. On some natural classes of inputs, for instance, the
First Fit Decreasing heuristic finds an optimal solution more often than not.
The data leads to several startling conjectures; some have been proved, while
others remain open problems. Although the details concern the particular
problem of bin packing, the theme of this talk is more general: how should
computer scientists use simulation programs to discover mathematical laws?
(This work was performed jointly with D.S. Johnson, F.T. Leighton and C.A.
McGeoch. Tom Leighton will give a talk on March 12 describing proofs of some
of the conjectures spawned by this work.)
HOST: Professor Tom Leighton
THIS SEMINAR IS JOINTLY SPONSORED BY THE COMBINATORICS SEMINAR & THE THEORY OF
COMPUTATION SEMINAR