Given a set of numbers, the number partitioning problem is to divide them into two or more subsets so that the sum of the numbers in each subset are as nearly equal as possible. Number partitioning is the simplest NP-Complete problem to describe, and is contained in many scheduling applications. We present a number of algorithms for finding approximate and optimal solutions to both two-way and multi-way number partitioning. Surprising, number partitioning actually gets easier for large instances, and even very large instances can be optimally solved in practice.
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). Korf is the recipient of a 1985 IBM Faculty Development Award, a 1986 NSF Presidential Young Investigator Award, and the Lockheed Martin Excellence in Teaching Award in 2005. He was elected a Fellow of the Association for the Advancement of Artificial Intelligence in 1994.