Counterexamples to the Greedy Algorithm

Question

In the graph theory section of my Discrete Math course I'll be covering Prim's Algorithm for finding the minimal spanning tree. I'd like to impress upon the students just how special it is that the greedy approach actually works. To do this, it'd be nice to have a variety of easy to understand problems where the greedy algorithm fails to produce the optimal solution.

What are some good examples of problems where the greedy algorithm fails?

The only example I can think of is Egyptian fraction decomposition where taking the next largest unit fraction does not always give the shortest decomposition. But the students don't have much number theory background and I feel like this problem already requires too much introduction. Ideally it'd be nice to have 2 or 3 problems that could be demonstrated quickly in one class period.

(More details: The students in the course have had Calculus and we will have covered Logic, Sets, Recursion, and the basics of Graph Theory by then.)

Answer 1

The greedy algorithm fails quite spectacularly for the Traveling Salesman Problem (TSP):

Bang-Jensen, Jørgen, Gregory Gutin, and Anders Yeo. "When the greedy algorithm fails." Discrete Optimization 1.2 (2004): 121-127. (PDF download.)

Abstract. We provide a characterization of the cases when the greedy algorithm may produce the unique worst possible solution for the problem of finding a minimum weight base in an independence system when the weights are taken from a finite range. We apply this theorem to TSP and the minimum bisection problem. The practical message of this paper is that the greedy algorithm should be used with great care, since for many optimization problems its usage seems impractical even for generating a starting solution (that will be improved by a local search or another heuristic).

Here is a little example from S.K.Basu's book, Design Methods and Analysis of Algorithms:

---

                   
^{From $A$, the greedy cycle is $ABDCA$ of length $9$, while $ACBDA$ has length $8$.}

---

Answer 2

There are tons of tasks where greedy algorithms fail, but the best in my opinion is the change-making problem. It is great, because whether the obvious greedy algorithm works depends on the input (i.e. the denominations). For example, if you have coins $1,6,8$, then $12=6+6$ is better than $12=8+1+1+1+1$.

Some other tasks:

• Shortest paths where the edge labels do not have to be positive.
• Maximum independent set (strategy: consider sequentially vertices ordered by their degree).
• This problem.

I hope this helps $\ddot\smile$