Largest differencing method
In computer science, Karmarkar-Karp number partitioning is an algorithm for solving the partition problem and the multiway number partitioning. It is called after its inventors, Narendra Karmarkar and Richard M. Karp.[1]
An approximate algorithm
The differencing heuristic (also called the Karmarkar-Karp heuristic) sorts the numbers in descending order. For k=2, it works as follows. It takes the two largest numbers, removes them from S, and replaces them with their difference (this represents a decision to put each of these numbers in a different subset). It proceeds in this way until a single number remains, which is the sum-difference. The subsets can be reconstructed by backtracking. The runtime complextiy of the approximate algorithm is O(n log n).
For example, if S = {8,7,6,5,4}, then the resulting difference-sets are 6,5,4,1, then 4,1,1, then 3,1 then 2, which can be backtracked to the 2-way partitions {3},{1}, then {4},{1,1}, then {4,7}, {1,8}, then {4,7,5}, {8,6}, where the sum-difference is 2. Note that this partition is not optimal: in the partition {8,7}, {6,5,4} the sum-difference is 0. On random instances, this approximate algorithm performs much better than greedy number partitioning.
An exact algorithm
The complete Karmarkar-Karp algorithm (CKK) finds an optimal solution in the following way. It constructs a tree of degree . Each level corresponds to a pair of numbers, and each of the branches corresponds to a different way to allocate them into the k sets. For example, with k=2 there are two branches: in one branch the two largest numbers are replaced with their difference (corresponding to putting these numbers in different subsets), and in the other branch they are replaced with their sum (corresponding to putting them in the same subset). This algorithm finds the KK solution first, but then proceeds to find better solutions.
For k=2, CKK runs substantially faster than the Complete Greedy Algorithm (CGA) on random instances. This is due to two reasons: when an equal partition does not exist, CKK often allows more trimming than CGA; and when an equal partition does exist, CKK often finds it much faster and thus allows earlier termination.[2]
References
- ^ Narendra Karmarkar and Richard M. Karp, "The differencing method of set partitioning", Tech report UCB/CSD 82/113, Computer science division, University of California, Berkeley, 1982
- ^ Korf, Richard E. (1995-08-20). "From approximate to optimal solutions: a case study of number partitioning". Proceedings of the 14th international joint conference on Artificial intelligence - Volume 1. IJCAI'95. Montreal, Quebec, Canada: Morgan Kaufmann Publishers Inc.: 266–272. ISBN 978-1-55860-363-9.