Greedy Algorithms

Jun 3rd, 2013

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.

Greedy stays ahead

The method is good when there is a value that we are maximizing (or minimizing). We show that the Greedy algorithm produces, at each step of the algorithm, a larger (or lower) value than any other algorithm.

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$)
  Here, it is problem specific.

• Conclusion. Because Greedy is ahead after each choice, Greedy is ahead at the end of the algorithm, and therefore produces an optimal solution.

Comments