---
title: "From Approximate to Optimal Solutions: A Case Study of Number Partitioning"
authors:
  - "Richard E. Korf"
doi: ""
url: "https://ijcai.org/proceedings/1995/35"
pdf: "https://ijcai.org/proceedings/1995/0035.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "266-271"
track: "Automated Reasoning"
keywords:
---

# From Approximate to Optimal Solutions: A Case Study of Number Partitioning

Richard E. Korf

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 266-271.

## Abstract

Given a set of numbers, the two-way partitioning problem is to divide them into two subsets, so that the sum of the numbers in each subset are as nearly equal as possible. The problem is NP-complete, and is contained in many scheduling applications. Based on a polynomial-time heuristic due to Karmarkar and Karp, we present a new algorithm, called Complete Karmarkar Karp (CKK), that optimally solves the general number-partitioning problem. CKK significantly outperforms the best previously-known algorithms for this problem. By restricting the numbers to twelve significant digits, we can optimally solve two-way partitioning problems of arbitrary size in practice. CKK first returns the Karmarkar-Karp solution, then continues to find better solutions as time allows. Almost five orders of magnitude improvement in solution quality is obtained within a minute of running time. Rather than building a single solution one element at a time, CKK constructs subsolutions, and combines them in all possible ways. CKK is directly applicable to the 0/1 knapsack problem, since it can be reduced to number partitioning. This general approach may also be applicable to other NP-hard problems as well.