Greedy algorithms
Also known as: Greedy algorithms · greedy · exchange argument · set cover · matroid · canonical coin systems
Take the step that looks best right now and never reconsider it. Sometimes this gives the best answer, and it can be proved; sometimes the answer is close to the best, and one can say how close; and sometimes greed confidently lies. How to tell one from another, on a print shop's deadlines, change in coins and radio towers over 675 villages of Moravia.
The 675 villages and towns of South Moravia need to be connected. A tower placed in a settlement covers everything within ten kilometres. How many towers are needed? A greedy way suggests itself: put the next tower where it will cover the most settlements not yet covered. It is fast, clear and almost never hits the best answer. Below is greed against the exact optimum, found beforehand by an integer programming solver.
With a radius of 10 km greed puts up 40 towers, while 29 would do: it is 1.38 times worse. With 20 km, 13 towers instead of 9. The first greedy towers stand where many small villages are close together, not by Brno: the function counts settlements, not inhabitants. Each greedy step was reasonable, and the outcome is not. This is a typical story, and the whole art of greedy algorithms is understanding in which problems it does end well after all.
The idea
Build the answer step by step and at each step take what looks best now: the earliest deadline, the largest coin, the shortest edge, the most profitable place. The choice is not reconsidered. The algorithm comes out simple and fast, but correct only if the problem has a special structure, and that structure has to be proved.
Three outcomes come up all the time. Greed is right: proved by an exchange argument or by the greedy answer matching a lower bound. Greed is almost right: it does not find the best answer, but it is guaranteed to be no worse than the best by a known factor. Greed lies, and then exhaustive search or dynamic programming is needed. How this looks at a till, in the timetable of one crew, in a power grid and in compression is told in the course chapter “Greed and electricity”. Here are three other stories.
When it is right: the exchange argument
A print shop has one press and eight orders. Each takes the press for a few hours and is promised by a certain hour. An order finished after its deadline is late; we want the largest lateness to be as small as possible. Try different orders and rules:
“As they came” is 10 hours late, “shortest first” 7, “by deadline” 3. Going over all 40,320 orders in the listing below confirms it: less than three hours is impossible. The rule “first what is due earliest” was devised by James Jackson in 1955, and it holds for any orders.
If the orders are done in increasing order of deadline, the largest lateness is the smallest possible.
Take any order. If somewhere in it order A stands right before B while A’s deadline is later, swap them. Everything before and after this pair finishes at the same moments. The pair together finishes at the same moment t. After the swap B finishes earlier than before, so its lateness has not grown. A now finishes at t, and A’s lateness at moment t is no greater than B’s lateness at moment t was, since A’s deadline is later. So the largest lateness has not grown. A swap reduces the number of pairs “out of deadline order”, so in a finite number of swaps any order turns into the deadline order without ever getting worse. So the deadline order is no worse than any other.
This is the exchange argument: any solution turns step by step into the greedy one, and no step spoils it. Press “Exchange” in the scene and watch the number: it never grows. The rule “shortest first” cannot be proved by exchange, and the scene shows that it is wrong too.
The second way to prove greed is to show that its answer matches a lower bound. This is how the meeting rooms problem is solved: if at some moment d meetings are going on at once, fewer than d rooms are impossible, while the greedy assignment by start time opens a new room only when all the open ones are busy, that is, exactly at such a moment. In detail in the first problem of the article.
When it lies: coins
Greedy change takes each time the largest coin that fits. With tenge coins it always gives the fewest coins, but add a 25 coin to the purse, and 40 is paid as 25 + 10 + 5 instead of 20 + 20. Coin sets on which greed is always right are called canonical. Check any set of your own:
There is no need to check all amounts to infinity. In 1994 Dexter Kozen and Shmuel Zaks proved that if greed fails somewhere, it already fails on an amount less than the two largest coins added together. So the scene checks only the amounts up to this bound, comparing greed with dynamic programming, and if everything matched there, the answer “always right” is proved. In 2005 David Pearson found an even faster check, in a number of steps cubic in the number of denominations rather than in their size.
When it is almost right: cover
Back to the towers. The set cover problem is NP-hard: no fast exact algorithm is known for it, and the solver from the scene simply searches cleverly and does not always make it in time. But about greed one can say how much worse it is.
If one tower covers at most s settlements, the greedy cover is larger than the optimal one by a factor of at most H(s) = 1 + 1/2 + … + 1/s ≈ ln s.
Let the optimum be k towers. Split each greedy tower equally between the settlements it covered for the first time: if it covered m new settlements, each of them pays 1/m. The sum of all payments equals the number of greedy towers. Now take any tower of the optimum and its settlements. Greed covers them in turn. While j of them are still uncovered, this tower itself would cover j new settlements, so the greedy tower chosen at this step covers at least j, and each of its new settlements pays at most 1/j. So the settlements of one optimal tower pay together at most 1 + 1/2 + … + 1/s = H(s), and the settlements of all k towers at most k·H(s). Each settlement is covered by some tower of the optimum, so this bounds the whole sum, that is, the number of greedy towers.
For 10 km the richest tower covers 57 settlements, and the guarantee is H(57) ≈ 4.6. On the real data greed is at worst 1.38 times worse: the guarantee describes the worst case, not the usual one. But in general nothing better than the guarantee can be devised: Uriel Feige showed in 1998, and Irit Dinur and David Steurer finally proved in 2014, that if P ≠ NP, no fast algorithm gives a cover that is always less than (1 − ε) ln n times worse than the optimum.
When it is always right: matroids
There is a class of problems where greed is right for any weights: choose a set of elements of the largest weight subject to “the set is independent”. If the independent sets have two properties, that a subset of an independent set is independent, and that a smaller independent set can always grow towards a larger one by taking an element from it, then greed, “take the heaviest if it does not break independence”, is optimal. Such systems are called matroids. The forests in a graph are a matroid, and that is why greedy Kruskal builds a minimum spanning tree. Linearly independent vectors are a matroid. A coin set is not, a knapsack is not, and there greed lies. The converse holds too: if greed is right for any weights, the system is a matroid (Rado, 1957; Edmonds, 1971).
Code
The print shop: three rules and a check by going over all orders.
Checking a coin system by the Kozen–Zaks bound: greed against dynamic programming on all amounts below the two largest coins.
Towers over Moravia: the greedy cover for four radii and a comparison with the optimum, which was computed in advance and lies in the data; the program checks that it really covers all the settlements.
What it costs
Greedy algorithms are usually fast: a sort or a heap and one pass, O(n log n). The deadline order is a sort. Meeting rooms are a sort and a heap. Greedy cover done directly is more expensive: at each step recompute the gain of every tower, O(k·n²) for k towers and n settlements, but for 675 settlements that is a fraction of a second. The solver that found the optimum thought for seconds on the same data, and on bigger problems it may think for years: that is the price of exactness.
The main cost of greed is not in time but in proof. A greedy algorithm is almost always easy to devise and write, and almost always easy to get wrong. Before trusting greed, look for a counterexample on small inputs by exhaustive search, as the coin scene does.
Problems
In the first greed is right, and a lower bound proves it; among the tests are duty shifts for all the earthquakes of the USGS catalogue. In the second greed has to be corrected: decide where to stop not at the station but later, when the fuel runs out.
How many rooms are needed Refuelling on the wayData: Places: GeoNames, CC BY 4.0