Greedy Algorithms

A greedy algorithm takes whichever step looks best right now and never reconsiders it. When the problem has the right shape, that one rule solves it, and nothing is faster. When it does not, greedy returns an answer that is confident, plausible and wrong, with no error and no warning.

The skill this topic teaches is telling the two cases apart. The tool for it is an argument short enough to retell: take the best possible answer, swap its first choice for the greedy one, and show that nothing gets worse. Where that swap works, greedy is exact. Where it fails, greedy is at best a heuristic, and the size of its error is a number someone has to know.

The Best Local Step

A greedy algorithm chooses by one rule at each step, such as the earliest finish, the cheapest edge or the rarest symbol, commits to the choice and moves on. There is nothing to undo, so the cost is usually one sort, from Chapter 7, or a heap, from Chapter 6, followed by a single pass: about n log n. So greedy algorithms are the first thing to try and the last thing to trust without checking.

When Greedy Is Provably Enough: Scheduling

To fit the most meetings into one room, repeatedly take the meeting that ends earliest among those that still fit. The figure applies the rule to eight meetings between 8:00 and 18:00. It takes B, which ends at 11:00, then D from 11:00 to 13:00, then E until 15:00, then G until 17:00: four meetings. A brute-force check of every subset of the eight confirms that four is the most that fit.

Two other plausible rules lose on the same input. Taking the earliest start first grabs A, which runs from 8:00 to 13:00 and blocks the whole morning, and ends with three meetings. Taking the shortest meeting first grabs C, one hour from 10:30, which overlaps both B and D, and also ends with three.

The argument for earliest finish fits in three sentences. Take any best schedule and look at its first meeting. Swap it for the meeting that ends earliest overall; that one ends no later, so nothing after it collides, and the schedule is no worse. Repeat for the second meeting, and the third, and the best schedule turns into the greedy one without ever losing a meeting.

The Same Proof Elsewhere

Huffman coding, from the Compression and Information topic in Chapter 2, repeatedly merges the two rarest symbols, and produces the shortest possible prefix code for known symbol frequencies. Dijkstra's algorithm settles the closest node, and Kruskal's and Prim's algorithms add the cheapest safe edge, all in Chapter 8. Each is greedy, and each is backed by its own swap argument of the kind above.

That argument is what separates a greedy algorithm from a guess. The style of the code, one pass with no backtracking, looks the same in both cases. Only the proof says whether the answer is the best one.

When Greedy Fails: Coin Change

Making change with the fewest coins looks like a textbook greedy problem: take the largest coin that fits, repeat. With coins of 1, 3 and 4, making 6 greedily takes a 4, then a 1, then another 1, three coins. Two 3s make 6 with two coins. The largest coin was the wrong first move, and greedy never reconsiders a move.

For euro and US coins, greedy happens to be optimal, because those coin sets have the right structure. Checked by computer against the true minimum for every amount up to 2,000 cents, greedy matches it for euro coins and for US coins every time. For 1, 3 and 4 it fails at 6, 10, 14 and every fourth amount after them: a quarter of all amounts up to 2,000. For arbitrary denominations the minimum comes from dynamic programming, which considers every way to make each smaller total.

Greedy as a Heuristic

Some problems have no known fast exact method at all; Chapter 14 names them. Packing jobs onto machines, or items into bins of fixed size, is one. Greedy is used for them anyway, and the question becomes how far from the best it can land. First-fit decreasing, which sorts items largest first and puts each into the first bin with room, never needs more than 11/9 of the optimal number of bins plus a fraction of one: about 22% more, a bound proved tight in 2007.

Other greedy rules have no bound at all. Filling a knapsack with indivisible items by best value per kilogram can miss badly: with room for 10 kilograms, one item of 1 kilogram worth 2 and one of 10 kilograms worth 10, greedy takes the small item first, has no room left for the large one, and ends with 2 where 10 was possible. Scale the large item up and the gap grows without limit. The difference between these two heuristics is a proof, not a feeling.

What a Greedy Choice Costs in Production

The optimal rule for evicting items from a cache, described by Belady in 1966, removes the item that will be needed furthest in the future. Nobody knows the future, so the LRU cache from Chapter 5 evicts the item used longest ago, as a greedy guess that the past predicts the future. One scan over more data than the cache holds breaks that guess completely: every item the scan touches is newer than everything useful, so the scan evicts the whole working set to make room for rows that are never read again.

A scheduler that places each new job on the least-loaded machine is greedy too, and it is fast and usually good enough. The price of greedy in both cases is the answers it never looked at, and that price is paid silently: no log line says "a better answer existed".