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.

An approximate algorithm

The largest differencing heuristic (also called the Karmarkar–Karp heuristic) sorts the numbers in descending order. For k=2, it operates in two phases. In the first phase, 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. In the second phase, the subsets are 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. 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.