# Greedy Algorithms

This article presents the two most common startegies to prove the correctness of Greedy algorithms.

### Exchange argument for Greedy algorithms

The Greedy solution $\text{Gr}$ makes a sequence of choices, and an optimal solution $\text{OPT}_0$ makes another sequence of choices.

$\left\{ \begin{array}{ll} \text{Gr} & = C_1, C_2, ... \\ \text{OPT}_0 & = C_1', C_2', ... \end{array} \right.$

We are going to build by induction a sequence of optimal solutions where the last one agrees with $\text{Gr}$ on all the choices (proving that $\text{Gr}$ is optimal)

$\text{OPT}_0 \to \text{OPT}_1 \to ... \to \text{OPT}_n = \text{Gr}$

and $\text{OPT}_i$ agrees with $\text{Gr}$ up to the $i$th choice:

$\left\{ \begin{array}{ll} \text{Gr} & = C_1, C_2, ..., C_i, C_{i+1},... \\ \text{OPT}_i & = C_1, C_2, ..., C_i, C_{i+1}',... \end{array} \right.$
• Base case. $\text{OPT}_0$ agrees with $\text{Gr}$ up to choice zero (vacuously true).

• Inductive step. Suppose we have an optimal solution $\text{OPT}_i$ agreeing with $\text{Gr}$ up to choice $i$. We need to transform

$\text{OPT}_i \to \text{OPT}_{i+1}$

such that it agrees also on choice $i+1$ and it is still optimal. Here, it is problem specific.

• Conclusion. We have built an optimal solution $\text{OPT}_n$ agreeing with $\text{Gr}$ on all choices. Therefore, $\text{Gr} = \text{OPT}_n$ is optimal.

Let $V_0 = 0, V_1, V_2, …$ the values of the Greedy algorithm after each choice, and $V_0’ = 0, V_1’, V_2’, …$ the values of any other algorithm. Let’s prove by induction on $i$, that after each choice $i$, $V_i \geq V_i’$.
• Base case. $V_0 = 0 = V_0’$ so Greedy is ahead before any choice.
• Inductive step. Assume $V_i \geq V_i’$ (Greedy was ahead before the choice $i+1$). We need to show that $V_{i+1} \geq V_{i+1}’$ (Greedy is ahead after the choice $i+1$)