A complete anytime algorithm for number partitioning. - Korf, Richard E.
Given previous termanext term set of previous termnumbers,next term the two-way previous termnumber partitioningnext term problem is to divide them into two subsets, so that the sum of the previous termnumbersnext term in each subset are as nearly equal as possible. The problem is NP-previous termcomplete.next term Based on previous termanext term polynomial-time heuristic due to Karmarkar and Karp, we present previous termanext term new previous termalgorithm,next term called previous termCompletenext term Karmarkar-Karp (CKK), that optimally solves the general previous termnumber-partitioningnext term problem, and significantly outperforms the best previously-known previous termalgorithmsnext term for large problem instances. For previous termnumbersnext term with twelve significant digits or less, CKK can optimally solve two-way previous termpartitioningnext term problems of arbitrary size in practice. For previous termnumbersnext term with greater precision, CKK first returns the Karmarkar-Karp solution, then continues to find better solutions as time allows. Over seven orders of magnitude improvement in solution quality is obtained in less than an hour of running time. Rather than building previous termanext term single solution one element at previous termanext term time, or modifying previous terma completenext term solution, CKK constructs subsolutions, and combines them together in all possible ways. This approach may be effective for other NP-hard problems as well.
Keywords: Number partitioning; Anytime algorithm; NP-complete.