Largest differencing method

In computer science, Karmarkar–Karp number partitioning (also called the largest differencing method) 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.

An approximate algorithm

The input to the algorithm is a set S of numbers, and a parameter k. The required output is a partition of S into k subsets, such that the sums in the subsets are as nearly equal as possible. The main steps of the algorithm are:

1. Sort the numbers in descending order.
2. Repeatedly replace numbers by their difference, until one number remains.
3. Using backtracking, compute the partition.

Two-way partitioning

For k=2, step 2 operates 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. This single number is the difference in sums between the two subsets. 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.

Step 3 constructs the subsets in the partition by backtracking.

In the second phase, the subsets are reconstructed by backtracking. The runtime complextiy of the approximate algorithm is O(n log n).

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.

3-way partitioning

On random instances, this approximate algorithm performs much better than greedy number partitioning. However, it is still bad for instances where the numbers are exponential in the size of the set.

Implementation

The following Java code implements the first phase of Karmarkar–Karp. It uses a heap to efficiently find the pair of largest remaining numbers.

int karmarkarKarpPartition(int[] baseArr) {	
    // create max heap	
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>(baseArr.length, REVERSE_INT_CMP);

    for (int value : baseArr) {		
        heap.add(value);	
    }

    while (heap.size() > 1) {
        int val1 = heap.poll();	
        int val2 = heap.poll();	
        heap.add(val1 - val2);
    }

    return heap.poll();
}

An exact algorithm

The complete Karmarkar–Karp algorithm (CKK) finds an optimal solution in the following way. It constructs a tree of degree $k!$. Each level corresponds to a pair of numbers, and each of the $k!$ 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. Korf reports that CKK can optimally partition 40 15-digit double-precision numbers in about 3 hours, while CGA requires about 9 hours.

Previous mentions

An algorithm equivalent to the Karmarkar-Karp differencing heuristic is mentioned in ancient Jewish legal texts by Nachmanides and Joseph ibn Habib. The algorithm is used to combine different testimoines about the same loan.