Computer Science

Colloquium Details

Optimal Bin Packing

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 appears to be asymptotically faster than the best existing optimal bin-packing algorithm, and outperforms it by over three orders of magnitude in running time on problems of size 60.

Biography

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, heuristic search, and planning in artificial intelligence. He is the author of "Learning to Solve Problems by Searching for Macro-Operators" (Pitman, 1985). He serves on the editorial boards of Artificial Intelligence, and the Journal of Applied 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 first UCLA School of Engineering Student's Choice Award for Excellence in Teaching in 1996. He is a Fellow of the American Association for Artificial Intelligence.