In computer science, the largest differencing method is an algorithm for solving the partition problem and the multiway number partitioning. It is also called the Karmarkar–Karp algorithm after its inventors, Narendra Karmarkar and Richard M. Karp. It is often abbreviated as LDM.
The 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:
Order the numbers from large to small. Replace the largest and second-largest numbers by their difference. If two or more numbers remain, return to step 1. Using backtracking, compute the partition.
Two-way partitioning
For k=2, the main step (2) works as follows.
Take the two largest numbers in S, remove them from S, and insert their difference (this represents a decision to put each of these numbers in a different subset). Proceed 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} after taking out the largest two numbers { 8,7} and inserting the difference 8-7=1 back; Repeat the steps and then we have { 4,1,1}, then { 3,1} then { 2}.
Step 3 constructs the subsets in the partition by backtracking. The last step corresponds to { 2},{ }. Then 2 is replaced by 3 in one set and 1 in the other set: { 3},{ 1}, then { 4},{ 1,1}, then { 4,5}, { 1,6}, then { 4,7,5}, { 8,6}, where the sum-difference is indeed 2.
The runtime complexity of this algorithm is dominated by the step 1 (sorting), which takes O(n log n).
Note that this partition is not optimal: in the partition { 8,7}, { 6,5,4} the sum-difference is 0. However, there is evidence that it provides a "good" partition:
If the numbers are uniformly distributed in [0,1], then the expected difference between the two sums is . This also implies that the expected ratio between the maximum sum and the optimal maximum sum is . When there are at most 4 items, LDM returns the optimal partition. LDM always returns a partition in which the largest sum is at most 7/6 times the optimum. This is tight when there are 5 or more items. 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.
Multi-way partitioning
For any k ≥ 2, the algorithm can be generalized in the following way.
Initially, for each number i in S, construct a k-tuple of subsets, in which one subset is { i} and the other k-1 subsets are empty. In each iteration, select two k-tuples A and B in which the difference between the maximum and minimum sum is largest, and combine them in reverse order of sizes, i.e.: smallest subset in A with largest subset in B, second-smallest in A with second-largest in B, etc. Proceed in this way until a single partition remains.
Examples:
If S = { 8,7,6,5,4} and k=2, then the initial partitions are ({ 8},{ }), ({ 7},{ }), ({ 6},{ }), ({ 5},{ }), ({ 4},{ }). After the first step we get ({ 6},{ }), ({ 5},{ }), ({ 4},{ }), ({ 8},{ 7}). Then ({ 4},{ }), ({ 8},{ 7}), ({ 6},{ 5}). Then ({ 4,7},{ 8}), ({ 6},{ 5}), and finally ({ 4,7,5},{ 8,6}), where the sum-difference is 2; this is the same partition as described above. If S = { 8,7,6,5,4} and k=3, then the initial partitions are ({ 8},{ },{ }), ({ 7},{ },{ }), ({ 6},{ },{ }), ({ 5},{ },{ }), ({ 4},{ },{ }). After the first step we get ({ 8},{ 7},{ }), ({ 6},{ },{ }), ({ 5},{ },{ }), ({ 4},{ },{ }). Then ({ 5},{ },{ }), ({ 4},{ },{ }), ({ 8},{ 7},{ 6}). Then ({ 5},{ 4},{ }), ({ 8},{ 7},{ 6}), and finally ({ 5,6},{ 4,7},{ 8}), where the sum-difference is 3. If S = { 5,5,5,4,4,3,3,1} and k=3, then after 7 iterations we get the partition ({ 4,5},{ 1,4,5},{ 3,3,5}). This solution is not optimal; a better partitioning is provided by the grouping ({ 5,5},{ 3,3,4},{ 1,4,5}).
There is evidence for the good performance of LDM:
