Greedy algorithm

Greedy algorithms are algorithms that always make the choice that looks best at the moment — it makes a locally optimal choice hoping that leads to a globally optimal solution. They’re generally fast but often don’t get the optimal solution. Smarter greedy algorithms use a guess of what may happen in the future to make a better decision. Notably, greedy algorithms are good approximators for NP-complete problems.

Like dynamic programming, greedy algorithms rely on optimal substructure proofs. This is achievable primarily via contradiction — and the premise is that greedy solutions are built on top of other greedy solutions to smaller problems.

Principles

Greedy solutions rely on three principles:

• Greedy choice — the optimal solution agrees with the first greedy choice.
• Smaller subproblems — after making the greedy choice, the resulting subproblem reduces in size.
• Optimal substructure — an optimal solution contains optimal solutions to subproblems.

In particular, for problems where greedy is optimal, we must be able to prove optimality of the greedy approach, i.e., that if we made the greedy decision first, we’d be able to reach an optimal point.

The intuition behind when to pick greedy versus DP largely comes down to whether a greedy solution can “overshoot” or “undershoot”. DP solutions are viable for greedy problems, but we can get a more optimal solution with greedy.

Approach

When we’ve found a suitable greedy choice, the proof of correctness has a few steps we follow:

• Let $G=g_1,g_2,\cdots ,g_m$, where $G$ denotes a greedy solution.
• First greedy choice — there exists some optimal solution $J=j_1,\cdots ,j_n$ such that $g_1=j_1$ but past 1.
• Smaller subproblems — after making the choice $j_1=g_1$, then we should be left with a smaller subproblem.
• Optimal substructure — we must solve the subproblem optimally for the original solution to be optimal.
• Recurse the argument to conclude that $j_2=g_2,j_3=g_3$.
• Therefore there exists an optimal solution $J$ such that $J=G$.

Greedy choice property

This is the most important, and most arcane proof in our procedure. We note a few key ideas:

• For greedy problems, there can be multiple optimal solutions. In fact, there can be multiple greedy solutions to a single problem. This makes contradiction a difficult proof to pull off.
• Thus, it’s very easy to “come” to a contradiction when one might not exist.

In our proof, we first define $J$ as an optimal and $G$ as a greedy solution. If $j_1=g_1$, “then we’re done”. We still need to prove the case where $j_1\ne g_1$. Depending on the problem, we either have 1) every element in the set show up in our final answer (car building), or 2) only a subset of input elements (scheduling).

• In the first case, this implies that $g_1$ must appear somewhere in $J$. By the definition of the greedy choice (i.e., by how we constructed it), we should get an inequality. Like $p_{j_1}\le p_{g_1}=p_{j_m}$ for some $m>1$.
• In the second case, the order of selection doesn’t matter. Assume $g_1\notin J$, then $p_{g_1}\ge p_j$, $\forall j\in J$ by construction of $g_1$. If we construct a solution

Problems

Extra notes

one pitfall:

• different optimal solutions, not every optimal solution agrees with the greedy choice
• common mistake: they say $J$ is any optimal solution. suppose $g_1\ne j_1$.
• they “come” to a contradiction, where there might not exist one

final 2015:

• note $\le$. not <. first slide.
  • not a contradiction! because there can be multiple greedy solutions to a single problem
• we instead found another optimal solution that agrees with the first greedy choice
• optimal substructure: done via contradiction
  • strictly non-optimal, so strict inequality <
  • basically depends on original greedy choice we proved before being true

scheduling deadlines:

• again not actually a contradiction. we’re proving that $\exists$ an optimal solution that agrees with the greedy choice