Exchange Argument, in depth: proving greedy algorithms with swaps, Smith's rule, EDD and the transitivity trap

What an exchange argument proves

Let G be the greedy solution and O any optimal solution. If they are equal there is nothing to prove. Otherwise find the first place where they differ: the first position in a sequence, the first edge in sorted order, the first item chosen. Then exhibit an exchange: modify O at that point so it agrees with G for one more step, and prove the modification does not increase the cost (or decrease the value). Repeating the exchange turns O into G in a finite number of steps, each preserving optimality, so G is optimal.

Three obligations must be met, and most broken proofs skip one of them:

1. Feasibility. The exchanged solution must still be valid.
2. No loss. The exchange must not make the objective worse; equality is enough.
3. Progress. Each exchange must reduce a distance to G, such as the number of inverted pairs, so the process ends.

There are two common shapes. An element exchange swaps one component of O for the greedy choice, such as replacing a heavier edge with the lightest edge crossing a cut. An adjacent-swap exchange works on orderings: if two neighbouring items in O are in the opposite order from G, swap them. The related greedy stays ahead technique instead shows by induction that G is never behind O; it suits objectives that are counts.

The adjacent-swap template for sequencing

Sequencing problems ask for an order of n jobs. Fix any order and look at two adjacent jobs i and j, with total processing time T of everything before them. Swapping them changes only their own completion times: every job before is untouched, and every job after still starts at T + p_i + p_j. So the effect of the swap is a function of i, j and at most T, and can be computed by hand.

If that difference has the form "i before j is no worse whenever key(i) ≤ key(j)" for some key that does not depend on T, the proof finishes itself. Bubble sort turns any order into the key-sorted one by adjacent swaps, each removing one inversion without increasing cost, so the sorted order costs no more than an optimal one.

The phrase "for some key" carries the whole proof: the pairwise condition must come from a transitive ranking. Without one, the inversion-counting step falls apart, as a section below shows.

Worked example: Smith's rule

Single machine; each job j has processing time p_j and weight w_j; the cost is the weighted sum of completion times, Σ w_j C_j, where weight is how much a job's waiting hurts.

Put i immediately before j with T time already used. Then i finishes at T + p_i and j at T + p_i + p_j, contributing w_i(T + p_i) + w_j(T + p_i + p_j). Swapping gives w_j(T + p_j) + w_i(T + p_i + p_j). Subtract and every term with T cancels: (i first) minus (j first) equals w_j p_i − w_i p_j. So i first is no worse exactly when p_i / w_i ≤ p_j / w_j, a key independent of T: sorting by p / w is optimal. This is Smith's rule. Four jobs:

Sorting by p / w gives B, D, C, A with completion times 1, 3, 7 and 10 and cost 2 + 9 + 28 + 10 = 49. Brute force over all 24 orders confirms 49 is the minimum. Two plausible alternatives lose: shortest processing time first (B, D, A, C) costs 57, and heaviest first (C, D, B, A) costs 58. Compare by cross-multiplication rather than division, so zero weights and floating-point ratio ties cannot reorder jobs unpredictably:

import functools, itertools

def smith_order(jobs):
    # jobs: list of (name, p, w) with p >= 0, w >= 0, not both zero
    def cmp(a, b):
        left, right = a[1] * b[2], b[1] * a[2]      # p_a * w_b versus p_b * w_a
        if left != right:
            return -1 if left < right else 1
        return (a[0] > b[0]) - (a[0] < b[0])        # deterministic tie-break by name
    return sorted(jobs, key=functools.cmp_to_key(cmp))

def weighted_completion(order):
    t = cost = 0
    for _, p, w in order:
        t += p
        cost += w * t
    return cost

jobs = [("A", 3, 1), ("B", 1, 2), ("C", 4, 4), ("D", 2, 3)]
best = min(itertools.permutations(jobs), key=weighted_completion)
assert weighted_completion(smith_order(jobs)) == weighted_completion(best) == 49

Maximum lateness and earliest deadline first

Change the objective to the maximum lateness, the largest value of C_j − d_j where d_j is a due date. Take adjacent jobs i then j with d_i greater than d_j, an inversion with respect to deadlines. Before the swap, j finishes at T + p_i + p_j with lateness T + p_i + p_j − d_j. After the swap, j finishes earlier, and i finishes at that same time T + p_i + p_j but has the later deadline, so its new lateness is smaller than j's old lateness. Neither new value exceeds the old maximum of the pair, nothing else moves, and the swap does not increase the maximum. Sorting by due date, the earliest-due-date (EDD) rule, is optimal.

Three jobs: a with p = 4 and d = 4, b with p = 1 and d = 6, c with p = 2 and d = 7. EDD runs a, b, c, finishing at 4, 5 and 7, so the maximum lateness is 0. Shortest-first runs b, c, a and finishes a at 7, three units late. The proof covers only the worst lateness: minimising the number of late jobs needs a different greedy (Moore-Hodgson), and minimising total tardiness on one machine is NP-hard.

Element exchanges: cuts, merges and first choices

Not every greedy algorithm produces an order. Many pick a set, and their proofs swap one element at a time.

• Minimum spanning trees. Let e be the lightest edge crossing some cut. If an optimal tree T does not contain e, adding e to T creates a cycle that crosses the cut again at some edge f with weight at least w(e). T + e − f is still a spanning tree and weighs no more. That is the cut property; Kruskal and Prim are corollaries, as the Kruskal deep dive shows.
• Huffman coding. In some optimal prefix code the two least frequent symbols are deepest siblings: if not, swapping them there cannot increase the weighted depth. See Huffman coding.
• Activity selection. The activity that finishes first can replace the first activity of any optimal schedule, because it ends no later; see activity selection.

Matroids explain these element exchanges: greedy is optimal for every weighting exactly when the feasible sets form a matroid (matroids). Sequencing results like Smith's rule come from the adjacent-swap template instead.

The transitivity trap

The template invites a mistake: derive a pairwise condition R(i, j), plug it into a comparator and call a library sort. If R is not transitive there is no key, and the output depends on the input order.

The two-machine flow shop shows it with real numbers. Each job runs on machine 1 for a units, then on machine 2 for b units; minimise the time the last job leaves machine 2. Johnson's analysis of an adjacent pair gives the condition: i before j is no worse when min(a_i, b_j) ≤ min(a_j, b_i). It is tempting to sort by that. Take x = (4, 3), y = (2, 2) and z = (4, 4). Then x may precede y, since min(4, 2) = 2 ≤ min(2, 3) = 2; y may precede z, since 2 ≤ 2; but x may not precede z, since min(4, 4) = 4 exceeds min(4, 3) = 3. The order x, y, z is consistent at every adjacent pair, yet its makespan is 14, while y, z, x achieves 13. A sort that only checks neighbours can return the worse one.

Johnson's actual rule repairs this with a genuine key: jobs with a ≤ b first in increasing a, then the rest in decreasing b. On these three jobs it gives y, z, x with makespan 13.

import itertools

def makespan(order):
    m1 = m2 = 0
    for a, b in order:
        m1 += a                      # machine 1 finishes this job
        m2 = max(m2, m1) + b         # machine 2 starts when both are ready
    return m2

def johnson(jobs):
    first = sorted([j for j in jobs if j[0] <= j[1]], key=lambda j: j[0])
    last = sorted([j for j in jobs if j[0] > j[1]], key=lambda j: -j[1])
    return first + last

x, y, z = (4, 3), (2, 2), (4, 4)
assert makespan([x, y, z]) == 14
assert makespan(johnson([x, y, z])) == 13 == min(makespan(q) for q in itertools.permutations([x, y, z]))

Runtimes punish non-transitive comparators differently. C++ std::sort requires a strict weak ordering, and violating it is undefined behaviour. Java's TimSort may throw IllegalArgumentException with the message "Comparison method violates its general contract!" on some inputs only. Python's sort never complains.

A strange comparator can still be fine. To concatenate integers into the largest number, put a before b when the string a + b is at least b + a. That rearranges to the key a / (10^|a| − 1), so it is transitive; on [3, 30, 34, 5, 9] it yields 9534330, matching brute force, while reverse string order gives 9534303.

Turn every exchange proof into a test

An exchange proof has a mechanical shadow: on small inputs, brute force can check the claim exactly. Three tests catch nearly every real bug.

import itertools, random

def check_greedy(greedy, cost, gen, trials=2000, seed=0):
    rng = random.Random(seed)
    for _ in range(trials):
        jobs = gen(rng)
        best = min(cost(list(q)) for q in itertools.permutations(jobs))
        got = cost(greedy(jobs))
        assert got == best, (jobs, got, best)
        shuffled = jobs[:]
        rng.shuffle(shuffled)
        assert cost(greedy(shuffled)) == got, jobs   # input order must not matter

def find_intransitive(before, gen_item, trials=100000, seed=0):
    rng = random.Random(seed)
    for _ in range(trials):
        x, y, z = gen_item(rng), gen_item(rng), gen_item(rng)
        if before(x, y) and before(y, z) and not before(x, z):
            return x, y, z                           # counterexample
    return None

gen = lambda r: [(str(i), r.randint(0, 6), r.randint(1, 6)) for i in range(r.randint(1, 6))]
check_greedy(smith_order, weighted_completion, gen)
naive = lambda i, j: min(i[0], j[1]) <= min(j[0], i[1])
print(find_intransitive(naive, lambda r: (r.randint(1, 4), r.randint(1, 4))))

The first test compares the greedy cost with brute force on 2,000 random instances of up to six jobs, then shuffles the input and requires the same cost. The second searches for a transitivity violation and finds one in the naive Johnson relation. Both run in seconds and belong in CI.

Where no exchange exists

When the exchange step cannot be completed, greedy is usually wrong, and the failed step tells you where. Coins of 1, 3 and 4 with target 6: greedy takes 4, 1 and 1, three coins, while 3 + 3 uses two. Try to exchange the optimal solution's first coin, a 3, for the greedy 4 and the remainder of 2 needs two coins instead of one; the no-loss obligation fails. The 0/1 knapsack fails the same way, since a better value-per-weight item can strand capacity. When a proof attempt fails, add the smallest counterexample it suggests to the test suite.

Operational guidance

• Sort by the key, not by a pairwise rule. Then the transitivity question disappears; use a comparator only for exactness, as in the cross-multiplied Smith comparator.
• Make ties deterministic. Any tie order is optimal, so choose a reproducible one such as job ID; otherwise diffs, caches and audits break.
• Guard the edges of the model. Smith's rule assumes non-negative weights; a job with zero weight has an infinite ratio and belongs at the end. EDD assumes every job is available at time zero; with release dates, minimising maximum lateness is NP-hard and EDD is only a heuristic.
• Re-prove when the objective changes. Sequence-dependent setup times, precedence constraints or a second machine can break the locality the swap relied on. If swapping two adjacent jobs now changes a third job's cost, the template no longer applies.
• Keep the brute-force oracle in CI. It protects the proof from refactors.

What to do next

1. List the greedy rules in your codebase and write next to each which proof shape justifies it: element exchange, adjacent swap or stays ahead.
2. For each sequencing rule, derive the two-job cost difference by hand and confirm that T cancels.
3. Express the result as a key. If you only have a pairwise relation, run find_intransitive before trusting any sort.
4. Add the permutation oracle and the shuffle test for instances of up to six items.
5. Write the model's assumptions (non-negative weights, no release dates, single machine) next to the code and assert them on input.
6. Read the matroids article to recognise the set problems where greedy is optimal for every weighting, and where it is not.