Google Research

Optimal Multi-Way Number Partitioning

Journal of the ACM, vol. 65 (2018)

Abstract

The NP-hard number-partitioning problem is to separate a multiset S of n positive integers into k subsets such that the largest sum of the integers assigned to any subset is minimized. The classic application is scheduling a set of n jobs with different runtimes on k identical machines such that the makespan, the elapsed time to complete the schedule, is minimized. The two-way number-partitioning decision problem is one of the original 21 problems that Richard Karp proved NP-complete. It is also one of Garey and Johnson’s six fundamental NP-complete problems and the only one based on numbers.

This article explores algorithms for solving multi-way number-partitioning problems optimally. We explore previous algorithms as well as our own algorithms, which fall into three categories: sequential number partitioning (SNP), a branch-and-bound algorithm; binary-search improved bin completion (BSIBC), a bin-packing algorithm; and cached iterative weakening (CIW), an iterative weakening algorithm. We show experimentally that, for large random numbers, SNP and CIW are state-of-the-art algorithms depending on the values of n and k. Both algorithms outperform the previous state of the art by up to seven orders of magnitude in terms of runtime.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work