Summary

The greedy approach is simple: at each iteration of the algorithm, pick the seemingly best alternative out of all the possible alternatives. In other words, greedy solutions to problems are applicable when choosing the locally 'best' alternative at each iteration leads to the globally optimal solution to the problem.

In this chapter, we looked at examples of problems where the greedy approach is optimal and leads to correct solutions to the given problem; that is, shortest-job-first scheduling. We also discussed how slightly modified versions of NP-complete problems such as the 0-1 knapsack and the graph coloring problem can have simple greedy solutions. This makes the greedy approach an important algorithm design tool for difficult problems. For problems that have a greedy solution, it is likely to be the simplest way to solve them; and even for problems that do not have a greedy solution, it can often be used to solve relaxed versions of the problem that might be &apos...