Largest differencing method

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 ${\displaystyle n^{-\Theta (\log(n)))}}$. This also implies that the expected ratio between the maximum sum and the optimal maximum sum is ${\displaystyle 1+n^{-\Theta (\log(n)))}}$ .[3]
• 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.[4] This is tight when there are 5 or more items.[2]
• 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.[5]

For any k ≥ 2, the algorithm can be generalized in the following way.[2]

• 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}).[2] 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:[2]

• Simulation experiments show that, when the numbers are uniformly random in [0,1], LDM always performs better (i.e., produces a partition with a smaller largest sum) than greedy number partitioning. It performs better than the multifit algorithm when the number of items n is sufficiently large. When the numbers are uniformly random in [o, o+1], from some o>0, the performance of LDM remains stable, while the performance of multifit becomes worse as o increases. For o>0.2, LDM performs better.
• Let f* be the optimal largest sum. If all numbers are larger than f*/3, then LDM returns the optimal solution. Otherwise, LDM returns a solution in which the difference between largest and smallest sum is at most the largest number which is at most f*/3.
• When there are at most k+2 items, LDM is optimal.
• When the number of items n is between k+2 and 2k, the largest sum in the LDM partition is at most ${\displaystyle {\frac {4}{3}}-{\frac {1}{3(n-k-1)}}}$ times the optimum,
• In all cases, the largest sum in the LDM partition is at most ${\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}}$ times the optimum, and there are instances in which it is at least ${\displaystyle {\frac {4}{3}}-{\frac {1}{3(k-1)}}}$ times the optimum.
• For two-way partitioning, when inputs are uniformly-distributed random variables, the expected difference between largest and smallest sum is ${\displaystyle n^{-\Theta (\log n)}}$.[3]