AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
A Hybrid Recursive Multi-Way Number Partitioning Algorithm
Richard Earl Korf

Last modified: 2011-06-28


The number partitioning problem is to divide a given set of N positive integers into K subsets, so that the sum of the numbers in each subset are as nearly equal as possible. While effective algorithms for two-way partitioning exist, multi-way partitioning is much more challenging. We introduce an improved algorithm for optimal multi-way partitioning, by combining several existing algorithms with some new extensions. We test our algorithm for partitioning 31-bit integers from three to ten ways, and demonstrate orders of magnitude speedup over the previous state of the art.

Full Text: PDF