Karmarkar-Karp Algorithm

Purpose: A heuristic for number partitioning — split a multiset of numbers into two subsets minimising the difference of their sums — that dramatically outperforms greedy. Also called the largest differencing method (LDM).

The Problem

Given $a_1,\dots ,a_n$, partition into $S$ and $\bar{S}$ minimising $\left|{\sum }_S{a}_i-{\sum }_{\bar{S}}{a}_i\right|$. NP-hard, though pseudo-polynomial via subset-sum DP in $O(n\sum a_i)$.

Greedy vs Differencing

Greedy (LPT). Sort descending, put each number in the currently lighter set. Simple, but the expected discrepancy for $n$ uniform random numbers in $[0,1]$ is $\Theta (1/n)$.

Karmarkar-Karp. Repeatedly take the two largest numbers and replace them by their difference — deferring the decision of whether they go in the same set or opposite sets, while committing to the fact that they will be separated.

while more than one number remains:
    remove the two largest, a >= b
    insert (a - b)
the single remaining number is the discrepancy

Expected discrepancy: $n^{-\Theta (\log n)}$ — superpolynomially better than greedy.

Code

long long karmarkarKarp(vector<long long> a) {
    priority_queue<long long> pq(a.begin(), a.end());
    while (pq.size() > 1) {
        long long x = pq.top(); pq.pop();
        long long y = pq.top(); pq.pop();
        pq.push(x - y);
    }
    return pq.empty() ? 0 : pq.top();
}

To recover the actual partition, keep a graph: each differencing step adds an edge between the two original elements meaning “these must be separated”. At the end, 2-colour the resulting forest.

Why differencing works

Greedy commits early and irreversibly. Differencing commits only to a relation (”$a$ and $b$ end on opposite sides”) and pushes the magnitude decision down the line. Each step reduces the largest value substantially, so the residual numbers shrink fast, and the final discrepancy is the accumulated residual rather than the accumulated greedy error.

Complexity

• Time: $O(n\log n)$ with a heap
• Space: $O(n)$
• Guarantee: none in the worst case — it is a heuristic. Worst-case ratio is $7/6$ for the related makespan objective.

Complete Karmarkar-Karp (CKK)

Turn the heuristic into an exact algorithm by branching: at each step, either difference the two largest (separate them) or sum them (keep them together). Explore the tree depth-first, taking the differencing branch first — the heuristic solution is found immediately and then improved.

With good pruning (stop when the largest remaining number exceeds the sum of the rest, which forces the answer), CKK solves $n\le 40$-$50$ exactly, well beyond what meet in the middle manages comfortably.

Which method when

$n$, values	Method
Small sum $\sum a_i\le 10^6$	subset-sum DP, or DP with bitset
$n\le 40$, huge values	meet in the middle, $O(2^{n/2})$
$n\le 50$, huge values	Complete Karmarkar-Karp
$n$ large, approximate answer fine	Karmarkar-Karp heuristic
$k$-way partition	KK generalises; also LPT greedy for makespan

Variants / Use Cases

• Subset Sum and Partition — the problem page
• Multiprocessor scheduling — the $k$-way version minimises makespan
• Approximation Algorithms — the topic page
• Phase transition — random partitioning instances show a sharp easy/hard transition at $m\approx n$ bits per number, a well-studied phenomenon