Greedy Algorithms

Greedy Algorithms #


  • Make choices one-at-a-time
  • Never look back
  • Hope for the best

However: does not work everywhere.

When to use greedy algorithms? #

Problem should exhibit optimal substructure:

  • Optimal solutions to a problem are made up from optimal solutions of subproblems
  • Each problem depends on only one subproblem

Common strategy for proving correctness #

  • Make a series of choices
    • Suppose we’re on track to make optimal solution T*
  • Show that at each step, choices won’t rule out a globally optimal solution
    • Suppose that T* disagrees with the next greedy choice
  • Manipulate T* in order to make a solution T that’s not worse but agrees with the next greedy choice
    • Swap choice k instead of choice j
  • After having made all choices, we haven’t ruled out an optimal solution, so the solution we found is optimal

This can be turned into an inductive proof.

Wrong greedy: unbounded knapsack #

Idea: select items with best value/weight ratio

  • This works if you can fill the entire knapsack capacity
  • However, if there is space left over, then we have a suboptimal solution

Correct greedy: activity selection #

Problem statement #


  • Activities a1…an
  • Start times s1…sn
  • Finish times f1…fn


  • Maximize the number of activities to do in a given day

Greedy algorithm #

  • Pick activity you can add with the smallest finish time
  • Repeat

What makes it greedy?

  • At each step in the algorithm, make a choice:
    • Can increase activity set by one
    • Leaving room for future choices
    • Do this and hope for the best
  • Hope that at the end of the day, this is a globally optimal solution

Correctness #

  • When we make a choice, we don’t rule out an optimal solution (i.e., there exists some optimal solution that contains that choice)
    • Suppose we have already chosen ai and there is still an optimal T* that extends our choices
    • Now consider the next choice ak
      • If ak in T*, we are done
      • If ak not in T*:
        • Let aj be the activity in T* with smallest finish time after ai
        • Consider schedule T swapping aj for ak
        • T is still allowed, since ak has smaller ending time than aj, so does not conflict with anything
        • T still optimal, since it has the same numer of activities as T*
  • The above is the inductive step of the proof of correctness.