Greedy Algorithms

A greedy algorithm constructs a solution to the problem by always making a choice that looks the best at the moment.

• Greedy algorithms are usually very efficient.
• The difficulty is find a greedy strategy that always produces a global optimal solution to the problem
• Often difficult to argue that a greedy algorithm works

Applications

• Interval Scheduling
• Minimum Sums
  • degree 1 → take median
  • Degree 2 → take average
• Huffman Coding

Example where greedy algorithm fails

Coin problem (use the least amount of coins to create a certain amount)

• Naive solution would be to try all combinations. However, we can act greedily
• Always try to use the largest coin until you are no longer able to. Then, switch to the next coin. This works with European coins.
• Counter example: You have coins $\{1,3,4\}$ and the target sum is $6$. The Greedy Algorithm will produce the solution $4+1+1$, but the correct solution is $3+3$
  • In this case, use Dynamic Programming

Proving Greedy Algorithms

I’ve figured out a small template for proving greedy algorithms.

Method #1

Assume the set $O$ generated by the optimal solution, and show that the greedy algorithm is as good as the optimal solution (prove this contradiction, assuming that greedy algorithm is worse than the optimal solution).

Example: see Interval Scheduling.

Method #2

Assume that the greedy algorithm uses $k$ things. Show that there is no other way for it to uses $k-1$ things. Thus, the greedy algorithm is optimal.