It is also called the Karmarkar–Karp algorithm after its inventors, Narendra Karmarkar and Richard M.
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}.
The runtime complexity of this algorithm is dominated by the step 1 (sorting), which takes O(n log n).
For two-way partitioning, when inputs are uniformly-distributed random variables, the expected difference between largest and smallest sum is
RLDM (Restricted Largest Differencing Method) works as follows.
[7] For two-way partitioning, when inputs are uniformly-distributed random variables, the expected difference between largest and smallest sum is
BLDM (Balanced Largest Differencing Method) works as follows.
For two-way partitioning, when inputs are uniformly-distributed random variables, the expected difference between largest and smallest sum is
[3] For multi-way partitioning, when c=ceiling(n/k) and each of the k subsets must contain either ceiling(n/k) or floor(n/k) items, the approximation ratio of BLDM for the minimum largest sum is exactly 4/3 for c=3, 19/12 for c=4, 103/60 for c=5, 643/360 for c=6, and 4603/2520 for c=7.
The ratios were found by solving a mixed integer linear program.
[10] The complete Karmarkar–Karp algorithm (CKK) finds an optimal solution by constructing a tree of degree
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.
[11] CKK can also run as an anytime algorithm: it finds the KK solution first, and then finds progressively better solutions as time allows (possibly requiring exponential time to reach optimality, for the worst instances).
[13] An algorithm equivalent to the Karmarkar-Karp differencing heuristic is mentioned in ancient Jewish legal texts by Nachmanides and Joseph ibn Habib.