Greedy arguments are a method of proving greedy algorithms
Greedy Stays Ahead
Works by showing that the greedy algorithm is at least as far ahead as the optimal solution, for every iteration
-
Define your solution. Your algorithm will produce some object X and you will probably compare it against some optimal solution X*. Introduce some variables denoting your algorithm’s solution and the optimal solution.
-
Define your measure. Your goal is to find a series of measurements you can make of your solution and the optimal solution. Define some series of measures m1(X), m2(X), …, mn(X) such that m1(X*), m2(X*), …, mk(X*) is also defined for some choices of m and n.
-
Prove greedy stays ahead. Prove that mi(X) ≥ mi(X*) or that mi(X) ≤ mi(X*), whichever is appropriate, for all reasonable values of i. This argument is usually done inductively.
-
Prove optimality. Using the fact that greedy stays ahead, prove that the greedy algorithm must produce an optimal solution. This argument is often achieved by contradiction, by assuming the greedy solution isn’t optimal and using the fact that greedy stays ahead to derive a proof by contradiction.
Exchange Argument
Works by showing that an optimal solution can be transformed into the greedy algorithm without any change in cost, thereby proving a greedy algorithm is optimal.
-
Define your solutions. You will be comparing your greedy solution X to an optimal solution X*, so it’s best to define these variables explicitly.
-
Compare solutions. Next, show that if X ≠ X*, then they must differ in some way. This could mean that there’s a piece of X that’s not in X*, or that two elements of X are in a different order in X*, etc. You might want to give those pieces names.
-
Exchange pieces. Show how to transform X* by exchanging some piece of X* for some piece of X. Then prove that by doing so you did not increase / decrease the cost of X* and therefore have a different optimal solution.
-
Iterate. Argue that you have decreased the number of differences between X and X* by performing the exchange, and that by iterating this process you can turn X* into X without impacting the quality of the solution.