"Optimal Bin Packing"

11/30/2001: [time not recorded]
[location not recorded]

Abstract: In this talk, I will consider the NP-complete problem of bin packing. Given a set of numbers, and a set of bins of capacity C, find the minimum number of bins needed to contain all the numbers, such that the sum of the numbers assigned to any given bin is less than or equal to C. We will briefly consider two heuristic approximation algorithms for this problem, first-fit decreasing and best-fit decreasing. The main focus on the talk, however, will be a new algorithm for finding optimal or minimum-bin solutions. The algorithm relies heavily on the idea that certain packings of a given bin can never be worse than other packings, and only these undominated packings need be considered. Our algorithm outperforms the best existing optimal bin-packing algorithm by three orders of magnitude in running time.

About Richard E. Korf: Richard Korf is a Professor of computer science at the University of California, Los Angeles. He received his B.S. from M.I.T. in 1977, and his M.S. and Ph.D. from Carnegie-Mellon University in 1980 and 1983, respectively, all in computer science. From 1983 to 1985, he served as Herbert M. Singer Assistant Professor of Computer Science at Columbia University. His research is in the areas of problem solving, planning, and heuristic search in artificial intelligence. He is the author of "Learning to Solve Problems by Searching for Macro-Operators" (Pitman, 1985). He serves on the editorial board of the {\it Journal of Applied Intelligence} and {\it Artificial Intelligence}. Dr. Korf is the recipient of a 1985 IBM Faculty Development Award, a 1986 NSF Presidential Young Investigator Award, the first UCLA Computer Science Department Distinguished Teaching Award in 1989, and the UCLA Engineering School First Annual Student's Choice Award for Excellence in Teaching in 1996. He was elected a Fellow of the American Association for Artificial Intelligence in 1994.

Last updated: Mon Jun 19 17:44:06 2006