Objective Functions for Multi-Way Number Partitioning

Proceedings of the International Symposium on Combinatorial Search, 3

Volume

Vol. 3 No. 1 (2010): Third Annual Symposium on Combinatorial Search

Oral Presentations

The number partitioning problem is to divide a set of integers into a collection of subsets, so that the sum of the numbers in each subset are as nearly equal as possible. There are at least three natural objective functions for number partitioning. One is to minimize the largest subset sum, another is to maximize the smallest subset sum, and the third is to minimize the difference between the largest and smallest subset sums. I show that contrary to my previous claims, no two of these objective functions are equivalent for partitioning numbers three or more ways. Minimizing the largest subset sum or maximizing the smallest subset sum correspond to different practical applications of number partitioning, and both allow a recursive strategy for finding optimal solutions that is very effective in practice. Finally, a completely new version of this recursive strategy appears to reduce the asymptotic complexity of the algorithm, and results in orders of magnitude improvement over the best previous results for multi-way partitioning.

10.1609/socs.v1i1.18172