{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T03:28:50Z","timestamp":1783049330537,"version":"3.54.6"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,7,25]],"date-time":"2018-07-25T00:00:00Z","timestamp":1532476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["0713178"],"award-info":[{"award-number":["0713178"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,8,31]]},"abstract":"<jats:p>The NP-hard number-partitioning problem is to separate a multiset<jats:italic>S<\/jats:italic>of<jats:italic>n<\/jats:italic>positive integers into<jats:italic>k<\/jats:italic>subsets such that the largest sum of the integers assigned to any subset is minimized. The classic application is scheduling a set of<jats:italic>n<\/jats:italic>jobs with different runtimes on<jats:italic>k<\/jats:italic>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\u2019s six fundamental NP-complete problems and the only one based on numbers.<\/jats:p><jats:p>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<jats:italic>n<\/jats:italic>and<jats:italic>k<\/jats:italic>. Both algorithms outperform the previous state of the art by up to seven orders of magnitude in terms of runtime.<\/jats:p>","DOI":"10.1145\/3184400","type":"journal-article","created":{"date-parts":[[2018,7,26]],"date-time":"2018-07-26T11:58:04Z","timestamp":1532606284000},"page":"1-61","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":49,"title":["Optimal Multi-Way Number Partitioning"],"prefix":"10.1145","volume":"65","author":[{"given":"Ethan L.","family":"Schreiber","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard E.","family":"Korf","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael D.","family":"Moffitt","sequence":"additional","affiliation":[{"name":"Google, Austin, Texas, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"H. B. Amor and J. V. de Carvalho. 2005. Cutting Stock Problems. Springer. H. B. Amor and J. V. de Carvalho. 2005. Cutting Stock Problems. Springer.","DOI":"10.1007\/0-387-25486-2_5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.08.036"},{"key":"e_1_2_1_3_1","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Joseph Y","author":"Chen B."},{"key":"e_1_2_1_4_1","unstructured":"V. Chvatal. 1983. Linear Programming. WH Freeman San Francisco CA. V. Chvatal. 1983. Linear Programming. WH Freeman San Francisco CA."},{"key":"e_1_2_1_5_1","unstructured":"E. G. Coffman Jr. and J. L. Bruno. 1976. Computer and Job-shop Scheduling Theory. John Wiley 8 Sons Hoboken NJ. E. G. Coffman Jr. and J. L. Bruno. 1976. Computer and Job-shop Scheduling Theory. John Wiley 8 Sons Hoboken NJ."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207001"},{"key":"e_1_2_1_7_1","unstructured":"E. G. Coffman Jr M. R. Garey and D. S. Johnson. 1997. Approximation algorithms for bin packing: A survey. Approximation Algorithms for NP-Hard Problems Dorit S. Hochbaum (Ed.). PWS Publishing Co. 46--93. E. G. Coffman Jr M. R. Garey and D. S. Johnson. 1997. Approximation algorithms for bin packing: A survey. Approximation Algorithms for NP-Hard Problems Dorit S. Hochbaum (Ed.). PWS Publishing Co. 46--93."},{"key":"e_1_2_1_8_1","unstructured":"G. B. Dantzig and M. N. Thapa. 1997. Linear Programming 1: Introduction. Vol. 1. Springer. G. B. Dantzig and M. N. Thapa. 1997. Linear Programming 1: Introduction. Vol. 1. Springer."},{"key":"e_1_2_1_9_1","unstructured":"G. B. Dantzig and M. N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Vol. 1. Springer. G. B. Dantzig and M. N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Vol. 1. Springer."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.8.1.101"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1070.0246"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.7.2.191"},{"key":"e_1_2_1_13_1","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"D\u00f3sa G."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.5.259"},{"key":"e_1_2_1_15_1","unstructured":"A. S. Fukunaga and R. E. Korf. 2005. Bin Completion Algorithms for Packing and Knapsack Problems. PhD Dissertation. University of California at Los Angeles. A. S. Fukunaga and R. E. Korf. 2005. Bin Completion Algorithms for Packing and Knapsack Problems. PhD Dissertation. University of California at Los Angeles."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622591.1622602"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800152.804907"},{"key":"e_1_2_1_18_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman San Francisco CA. M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman San Francisco CA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1958-10224-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1511\/2002.2.113"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"e_1_2_1_24_1","unstructured":"E. Huang and R. E. Korf. 2009. New improvements in optimal rectangle packing. In IJCAI. 511--516. E. Huang and R. E. Korf. 2009. New improvements in optimal rectangle packing. In IJCAI. 511--516."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"M. Iori and S. Martello. 2008. Scatter search algorithms for identical parallel machine scheduling problems. In Metaheuristics for Scheduling in Industrial and Manufacturing Applications. Springer 41--59. M. Iori and S. Martello. 2008. Scatter search algorithms for identical parallel machine scheduling problems. In Metaheuristics for Scheduling in Industrial and Manufacturing Applications. Springer 41--59.","DOI":"10.1007\/978-3-540-78985-7_2"},{"key":"e_1_2_1_26_1","unstructured":"D. S. Johnson. 1973. Near-optimal Bin Packing Algorithms. Ph.D. dissertation. Massachusetts Institute of Technology Cambridge MA. D. S. Johnson. 1973. Near-optimal Bin Packing Algorithms. Ph.D. dissertation. Massachusetts Institute of Technology Cambridge MA."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203025"},{"key":"e_1_2_1_28_1","unstructured":"N. Karmarkar and R. M. Karp. 1982. The Differencing Method of Set Partitioning. Computer Science Division (EECS) University of California. N. Karmarkar and R. M. Karp. 1982. The Differencing Method of Set Partitioning. Computer Science Division (EECS) University of California."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"R. M. Karp. 1972. Reducibility Among Combinatorial Problems. Springer. R. M. Karp. 1972. Reducibility Among Combinatorial Problems. Springer.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"H. Kellerer U. Pferschy and D. Pisinger. 2004. Knapsack Problems. Springer. H. Kellerer U. Pferschy and D. Pisinger. 2004. Knapsack Problems. Springer.","DOI":"10.1007\/978-3-540-24777-7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00086-1"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the National Conference on Artificial Intelligence. 731--736","author":"Korf R. E.","year":"2002"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1630659.1630838"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI\u201909)","author":"Korf R. E.","year":"2009"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI\u201911)","author":"Korf R. E.","year":"2011"},{"key":"e_1_2_1_36_1","volume-title":"23rd International Conference on Automated Planning and Scheduling.","author":"Korf R. E."},{"key":"e_1_2_1_37_1","volume-title":"International Symposium on Artificial Intelligence and Mathematics (ISAIM\u201914)","author":"Korf R. E."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/98124"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90094-S"},{"key":"e_1_2_1_40_1","first-page":"125","article-title":"The easiest hard problem: Number partitioning","volume":"125","author":"Mertens S.","year":"2006","journal-title":"Computational Complexity and Statistical Physics"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence. AAAI Press, 623--629","author":"Moffitt M. D.","year":"2013"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579085"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1033004"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-2361-4"},{"key":"e_1_2_1_45_1","unstructured":"F. J. Provost. 1993. Iterative weakening: Optimal and near-optimal policies for the selection of search bias. In AAAI. 749--755. F. J. Provost. 1993. Iterative weakening: Optimal and near-optimal policies for the selection of search bias. In AAAI. 749--755."},{"key":"e_1_2_1_46_1","unstructured":"V. Sarkar. 1989. Partitioning and Scheduling Parallel Programs for Multiprocessors. MIT Press Cambridge MA. V. Sarkar. 1989. Partitioning and Scheduling Parallel Programs for Multiprocessors. MIT Press Cambridge MA."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI\u201913)","author":"Schreiber E. L."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 28th Annual Conference on Artificial Intelligence (AAAI\u201914)","author":"Schreiber E. L."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210033"},{"key":"e_1_2_1_51_1","unstructured":"T. Walsh. 2009. Where are the really hard manipulation problems? The phase transition in manipulating the veto rule. In IJCAI. 324--329. T. Walsh. 2009. Where are the really hard manipulation problems? The phase transition in manipulating the veto rule. In IJCAI. 324--329."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/2871880.2871885"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02009683"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3184400","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3184400","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:29Z","timestamp":1750208909000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3184400"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,25]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3184400"],"URL":"https:\/\/doi.org\/10.1145\/3184400","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,25]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}