Looking for a significant example that highlights the suboptimality of the greedy algorithms A week from now, I'll have to present my work to a bunch of coworkers who aren't used to the optimisation world and terminology. One of the main algorithms I implemented uses a greedy type algorithm (a multi-start randomized greedy algorithm), and I'd really want to make two things very clear with simple examples : what the greedy algorithm is, and why it is suboptimal. 
I thought of giving examples with the shortest path problem, but I'm looking for real life examples, maybe situations where we naturally use a greedy approach unconsciously. 
Can you think of anything ?
 A: Putting coins into a vending machine, or making change. The objective is to minimise the number of coins used. A greedy algorithm uses the highest possible denomination coins first. Whether or not the greedy algorithm is optimal depends on the coin system. In both US system and the Euro system, the greedy algorithm actually is optimal. More info here.
A: Two natural algorithms to solve the traveling salesman problem (TSP) (finding a minimum cost "circular" tour (hamiltonion circuit) of the vertices of a complete graph) are greedy. One such algorithm is to start and home and visit next that vertex which is closest but which has not already been visited, and return home only when no other site is available to complete the tour. Another algorithm is to sort the edges in order of increasing size and form a tour by adding these edges in order of increasing cost so that one creates a circuit. It is not difficult to find examples where both of these algorithms generate tours which are not optimal.It is interesting that the second of these algorithms does work for finding a minimum cost spanning tree of a connected graph (in essence Kruskal's algorithm). A variant of the first algorithm also works for finding a minimum cost spanning tree and is known as Prim's algorithm.
A: Typical problems that require dynamic programming will usually fail miserably with a greedy algorithm. So, the knapsack problem comes to mind. 
Of course, shortest paths in a graph with negative weights is very easy to illustrate with very small graphs. Naive shortest path greedy algorithms on any graph also work. This immediately lends itself to a real-life application: planning the shortest path from point $A$ to point $B$ (e.g., car system GPS).  
A: One example that comes to mind, is problem of maximising a weighted independent set in a weighted graph, that is finding the largest weight subset of the vertex set, such that no two vertices in the subset have an edge between them. For a slightly unrealistic real world example, consider having a set of locations which have weights given by the expected profit obtained from opening a store there. Monopoly laws prevent the company from opening stores in towns connected by a single stretch of road. Now if our graph were to look like this, one central city which will make a little more profit than opening stores in each of the neighbouring towns, the greedy algorithm would be incredibly suboptimal. Indeed it is far better to open stores in all the towns than the city, but when the greedy algorithm picks the city first it rules out the possibility of opening stores anywhere else.

