Greedy Algorithms

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