Exchange arguments

A greedy rule can look right and still be wrong, so it needs a proof. The most common proof is an exchange argument. Take any best answer, and change it step by step into the greedy answer, without ever making it worse. Then the greedy answer is at least as good as the best one, so it is a best answer too.

How to prove a greedy method

Call the greedy answer G. Let B be any best answer; we know nothing about it except that no answer beats it. If B already equals G, there is nothing to prove. Otherwise, find a place where B does something the greedy rule would not do, and exchange it: change that part of B to what greedy does. Then show two things:

• the changed answer is still allowed (it breaks no rule of the problem);
• it is no worse than B.

The changed answer is still a best answer, and it is one step closer to G. Repeat until it equals G. Nothing was lost on the way, so G is as good as B.

Shortest job first

Jobs wait for one machine, which runs them one after another with no gaps. A job’s owner waits until the job finishes. In which order should the jobs run so that the total waiting time, the sum of all the finish times, is as small as possible? The greedy rule: the shortest job first. The figure starts from an order that breaks the rule and repairs it, one swap of neighbours at a time.

The exchange. Suppose a job x runs just before a shorter job y. Swap them. Every other job finishes at the same time as before, because the two together still take the same time. y now finishes earlier, by the length of x. x finishes later, by the length of y. So the total changes by len(y) − len(x), which is negative (len(x) means the length of x).

So an order with a longer job just before a shorter one is never the best: one swap improves it. A best order therefore has no such pair, which means it runs the jobs from shortest to longest. (Jobs of equal length can go in either order; the total is the same.)

The same result in one line. Call the job that runs first j₁, the second j₂, and so on up to jₙ: the small number is the job’s place in the order. The first job’s length is part of every job’s finish time, the second job’s length is part of all but one, and so on. So the total is n · len(j₁) + (n − 1) · len(j₂) + … + 1 · len(jₙ), where the dot · means times. The largest multiplier should go with the shortest job.

def least_total_wait(lengths):
    t = total = 0
    for length in sorted(lengths):   # shortest first
        t += length                  # this job finishes at t
        total += t
    return total

Earliest deadline first

Now each job also has a deadline. A job that finishes after its deadline is late by the difference; one that finishes on time is late by 0. The goal: make the largest lateness as small as possible. The greedy rule: run the jobs in order of deadline, earliest first. Switch the figure to “Least lateness”.

The exchange. Suppose x runs just before y, but y is due earlier. Let f be the time at which the second of the two finishes. Swap them:

• y now finishes earlier than before, so it is late by no more than before.
• x now finishes at f, so it is late by f − due(x) (due(x) is the deadline of x), or not at all. Before the swap, y finished at f and was late by f − due(y), which is more, because due(y) < due(x).
• No other job moves.

So the largest lateness does not go up. Repeating the swap turns any order into the deadline order without making it worse, so the deadline order is a best order. Notice that this proof says “no worse”, not “better”: that is enough.

The recipe

1. Say exactly what the greedy algorithm chooses.
2. Take any best answer. Find the first place where it differs from the greedy answer.
3. Exchange: change that part to the greedy choice. Show the result is still allowed and no worse.
4. Each exchange brings the answer closer to the greedy one, so after a finite number of them they are equal.

A neat way to count “closer” for orders is the number of inversions: pairs that are in the opposite order to the greedy order (SORT-1). Swapping an out-of-order pair of neighbours removes exactly one inversion, so at most n(n − 1) / 2 swaps are needed. The proof only needs the swaps to exist; nobody has to carry them out.

Back to the bag

Lesson 1’s rule (the most value per kg first) has an exchange proof too. Suppose a best bag holds less of the item with the most value per kg than it could. Then the bag either has empty space, or it holds a kilogram of some other item. Replace that kilogram (or fill that space) with a kilogram of the best item. The weight stays within the limit, and the value goes up or stays the same. Repeat until the bag matches the greedy bag.

This argument cuts a kilogram out of an item. When items must be taken whole, the exchange is not allowed, and indeed the rule fails (lesson 5).