Greedy Algorithms #

Idea:

• 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 #

Input:

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

Output:

• 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.