UCLA

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 run times onto k

identical machines such that the makespan, the time to complete the

schedule, is minimized. The two-way number-partitioning decision

problem is one of the original 21 problems Richard Karp proved

NP-complete. It is also one of Garey and Johnson's six fundamental

NP-complete problems, and the only one involving numbers.

This thesis explores algorithms for solving multi-way

number-partitioning problems optimally. We explore previously existing

algorithms as well as our own algorithms: sequential number

partitioning (SNP), a branch-and-bound algorithm; binary-search

improved bin completion (BSIBC), a bin-packing algorithm; cached

iterative weakening (CIW), an iterative weakening algorithm; and a

variant of CIW, low cardinality search (LCS). We show experimentally

that for high precision random problem instances, SNP, CIW and LCS are

all state of the art algorithms depending on the values of n and k.

All three outperform previous algorithms by multiple orders of

magnitude in terms of run time.