How to Learn Karmarkar–Karp Differencing: Number Partitioning, Largest-Difference Heuristics, Priority Queues and Anytime Search

Wait, What?

To split numbers into two nearly equal piles, one powerful idea is to keep taking the two biggest numbers and replacing them by their difference.

The number-partitioning problem is deceptively simple: divide a collection of positive numbers into two subsets whose sums are as close as possible. The problem is NP-hard, so for large general instances we should not expect a polynomial-time algorithm that always finds the optimum unless a major complexity-theory breakthrough occurs.

Karmarkar–Karp differencing is a classic high-quality heuristic. It repeatedly removes the two largest values, replaces them by their difference, and remembers that the two removed values should end up on opposite sides of the final partition. The last remaining value is the residue: the difference between the two subset sums produced by that chain of decisions.

At beginner level, this is a lesson about greedy transformations. At professional level, it becomes a study of priority queues, reconstruction, approximation versus optimality, complete differencing search, workload distributions and the danger of benchmarking a heuristic only on friendly inputs.

Quick Answer

Learn Karmarkar–Karp in this order: partition objective → greedy largest-two rule → differencing → residue → heap implementation → reconstructing the actual subsets → compare with greedy list scheduling → understand why it is a heuristic → complete Karmarkar–Karp search → pruning and bounds → random-instance behaviour → professional benchmarking.

1. The problem first

Given positive numbers:

a1, a2, ..., an

choose signs si ∈ {+1, -1} to minimise:

|s1*a1 + s2*a2 + ... + sn*an|

Equivalently, place each number in one of two subsets so that the absolute difference between subset sums is as small as possible.

If the final difference is zero, the partition is perfect.

2. A naive greedy method is not Karmarkar–Karp

A common beginner strategy sorts numbers descending and repeatedly places the next number into the currently lighter bin. That is a useful baseline, but it is a different heuristic.

Karmarkar–Karp instead asks: if the two largest values are x ≥ y, what if we commit to putting them on opposite sides? Their contribution to the final difference then behaves like x - y.

So replace:

x, y

with:

x - y

3. A hand example

Take:

10, 8, 7, 6, 5

Largest two: 10 and 8. Replace with 2:

7, 6, 5, 2

Largest two: 7 and 6. Replace with 1:

5, 2, 1

Largest two: 5 and 2. Replace with 3:

3, 1

Largest two: 3 and 1. Replace with 2.

The final residue is 2. That means the resulting partition has subset sums differing by two.

4. The final number is not the partition itself

If you only store numeric differences, you lose which original items belong on each side.

To reconstruct the partition, each heap item can carry a small expression tree. A leaf represents one original number. A differencing step combines two trees with the constraint “these two components must end up with opposite signs.”

After the final tree is built, traverse it assigning opposite signs across every differencing edge.

5. Sign reconstruction is a clean abstraction

Represent a combined item as:

Node(left, right)

meaning the left and right components must have opposite signs.

Then:

assign(node, sign):
    if leaf:
        output sign for this original item
    else:
        assign(node.left,  sign)
        assign(node.right, -sign)

One traversal recovers a valid pair of subsets consistent with the differencing decisions.

6. A max-heap gives the standard efficient implementation

Each iteration needs the two largest current values. That is exactly what a max-priority queue supports.

heapify all items
while heap size > 1:
    x = pop_max()
    y = pop_max()
    push(x - y)

With a binary heap, each pop or push costs O(log n), giving a straightforward O(n log n) implementation after heap construction.

7. Why “take the two largest” makes sense

Large numbers dominate the possible imbalance. By forcing the two largest current contributions onto opposite sides, the heuristic tries to cancel large-scale imbalance early.

The replacement x - y compresses the unresolved effect of those two items into a smaller residual contribution.

This is not a proof of optimality. It is the intuition behind a very effective greedy reduction.

8. The algorithm is a heuristic, not an exact solver

Karmarkar–Karp can produce excellent solutions, especially on many random instances, but there are instances where another sequence of decisions gives a smaller residue.

Do not write “Karmarkar–Karp solves number partitioning” without qualification. The polynomial-time largest-differencing method is a heuristic for an NP-hard optimisation problem.

9. Complete Karmarkar–Karp changes the game

A complete version explores alternative branches. For two selected values x ≥ y, there are two fundamental possibilities:

Different subsets: replace them by x - y.
Same subset: replace them by x + y.

The simple heuristic always takes the differencing branch. Complete search explores both branches, using good bounds and branch ordering to prune aggressively.

10. The heuristic becomes an upper bound for exact search

If the fast differencing heuristic quickly finds a residue R, then an exact search already knows that any branch incapable of beating R can be discarded.

This is an important professional pattern: a good heuristic can accelerate an exact algorithm even when the heuristic itself is not guaranteed optimal.

11. Lower bounds make pruning possible

Suppose the largest remaining value exceeds the sum of all others. Then even placing every smaller number against it cannot cancel it completely. This gives a lower bound on the final residue.

More sophisticated lower bounds can further reduce the search tree.

Exact-search engineering is therefore about branch order, bounds, duplicate-state reduction and memory discipline as much as about recursion.

12. Balanced partitioning adds another constraint

Sometimes the two subsets must contain nearly the same number of items, not merely similar sums. This is the balanced number-partitioning problem.

A differencing implementation that ignores cardinality cannot simply be declared a balanced solver. The state representation must carry the information needed to enforce the additional constraint.

13. Input scale and numeric representation matter

If numbers are integers, exact arithmetic is straightforward. If they are floating-point measurements, repeated differencing can introduce representation and comparison issues.

For high-reliability work, decide explicitly whether the objective is defined over integers, rationals, fixed-point values or floating-point approximations.

Two values that print the same may not compare exactly the same in binary floating point.

14. Stable tie-breaking improves reproducibility

If multiple heap items have equal values, arbitrary heap order can produce different but equally valid differencing trees.

For reproducible tests, include a deterministic secondary key such as an insertion sequence number or original-index signature.

Reproducibility is especially valuable when comparing algorithm versions.

15. A professional implementation stores provenance

Each heap item can store:

current difference value;
left child;
right child;
original item ID for leaves;
tie-break key;
optional cached total or cardinality metadata.

This allows reconstruction, debugging and independent verification.

16. Independent verification is easy and should always be done

After reconstructing the two subsets:

sumA = sum(items in A)
sumB = sum(items in B)
assert abs(sumA - sumB) == reported_residue
assert every original item appears exactly once

This validator is simple enough that there is little excuse not to run it.

17. Compare against multiple baselines

A meaningful benchmark should include:

random partition;
descending greedy placement into lighter bin;
Karmarkar–Karp differencing;
exact dynamic programming where sums are small enough;
complete search on moderate instance sizes.

This reveals where the heuristic’s advantage comes from and where it disappears.

18. Pseudopolynomial exact dynamic programming is an important counterpoint

When integer sums are modest, subset-sum dynamic programming can find an exact partition in time depending on the total sum rather than only on the number of items.

This teaches an important complexity lesson: “NP-hard” does not mean every real instance is hopeless. Input magnitude and structure matter.

19. Random-instance performance can be surprisingly strong

Classical analyses show that the largest-differencing method has excellent asymptotic behaviour under common random-input models. This helps explain why the heuristic is famous.

But random-input success does not imply worst-case guarantees. Always separate:

average/random-model behaviour
from
worst-case behaviour

20. Benchmark residues on a meaningful scale

Raw residue is useful, but a residue of 10 means different things when total weight is 100 versus 10 billion.

Also report a normalised measure such as:

residue / total_sum

or compare against the known optimum when available.

21. Tail behaviour matters for complete search

Exact branch-and-bound runtimes can vary dramatically across instances of similar size. Report median and high percentiles, not only averages.

An anytime solver should also report the best residue as a function of elapsed time so users can see how quickly useful solutions arrive.

22. How to teach this from beginner to professional

Predict: choose the next two numbers and compute their difference.
Run: trace a full differencing sequence by hand.
Investigate: reconstruct signs from the differencing tree.
Modify: replace the heap with a sorted list and measure the cost.
Make: implement both heuristic and complete versions with validators and benchmark baselines.

The sequence deliberately starts with visible state transitions and worked traces before asking learners to design the full implementation.

23. A strong trace table

step | largest x | second y | replacement | heap after step | provenance node

For exact search, extend it with:

branch | bound | best-known residue | pruned? | reason

24. Common failure states

Confusing Karmarkar–Karp with “put next item in the lighter bin.”
Reporting only the final residue and losing the actual partition.
Calling the heuristic exact.
Using floating-point values without defining tolerance semantics.
Using nondeterministic tie-breaking and then comparing irreproducible runs.
Benchmarking only random instances.
Comparing wall-clock times without validating solution quality.
Running exact search without a strong initial upper bound.

25. Practice ladder

Beginner: perform differencing by hand.
Foundation: implement a max-heap version that returns only residue.
Intermediate: reconstruct the full partition and add validation.
Advanced: implement complete differencing search with pruning.
Professional: build an anytime solver, compare heuristics and exact methods across random and adversarial distributions, record quality/time curves and verify every returned partition.

26. Ownership boundary

This article owns Karmarkar–Karp differencing as an algorithm-learning topic: number partitioning, differencing, priority queues, reconstruction, heuristic quality, complete search and benchmarking. It does not replace general scheduling theory, bin packing, integer programming, learner measurement or private system architecture.

Sources and further reading

Narendra Karmarkar and Richard M. Karp, “The Differencing Method of Set Partitioning,” UC Berkeley technical report CSD-83-113: Berkeley EECS archive.
Benjamin Yakir, “The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp,” Mathematics of Operations Research 21(1), 1996: DOI.
Stefan Boettcher and Stephan Mertens, “Analysis of the Karmarkar-Karp Differencing Algorithm”: Santa Fe Institute.
ACM/IEEE-CS/AAAI CS2023, Algorithmic Foundations: CS2023.
Sue Sentance, Jane Waite and Maria Kallia, PRIMM programming pedagogy: SIGCSE 2019.

Professional rule: you understand Karmarkar–Karp when you can distinguish the heuristic from exact partitioning, reconstruct and verify the actual subsets, explain why a heap gives efficient largest-item access, use the heuristic as an upper bound inside complete search, and evaluate quality across both friendly and adversarial workloads.

Small Group Tutorials