@article{Schreiber_Korf_2014, title={Cached Iterative Weakening for Optimal Multi-Way Number Partitioning}, volume={28}, url={https://ojs.aaai.org/index.php/AAAI/article/view/9122}, DOI={10.1609/aaai.v28i1.9122}, abstractNote={ <p> 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. We present a new algorithm, cached iterative weakening (CIW), for solving this problem optimally. It incorporates three ideas distinct from the previous state of the art: it explores the search space using iterative weakening instead of branch and bound; generates feasible subsets once and caches them instead of at each node of the search tree; and explores subsets in cardinality order instead of an arbitrary order. The previous state of the art is represented by three different algorithms depending on the values of n and k. We provide one algorithm which outperforms all previous algorithms for k >= 4. Our run times are up to two orders of magnitude faster. </p> }, number={1}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Schreiber, Ethan and Korf, Richard}, year={2014}, month={Jun.} }