Greedy Algorithms
A greedy algorithm makes the locally best choice at each step, which yields a global optimum only for problems with the right structure.
The strategy
A greedy algorithm builds a solution incrementally, always taking the option that looks best right now, never reconsidering. It is simple and fast, but the local-best choice leads to the global best only for problems with special structure. When that structure is absent, greedy becomes a heuristic with no guarantee.
When greedy is provably optimal
Greedy works when the problem has a matroid structure or exhibits the greedy-choice property and optimal substructure. In those cases a local optimum extends to a global one. Proving greedy correct usually requires an exchange argument showing any optimal solution can be transformed into the greedy one without loss.
Success stories
- Minimum spanning tree (Kruskal's and Prim's algorithms)
- Huffman coding for optimal prefix codes
- Dijkstra's shortest paths with non-negative weights
- Activity selection to maximize non-overlapping intervals
Where greedy fails
For the 0/1 knapsack problem, greedily taking the highest value-per-weight item can miss the optimum, because a locally good pick may block a better combination. There, dynamic programming is needed. Recognizing when greedy is safe versus merely heuristic is the key skill.
Greedy as approximation
Even when greedy is not exactly optimal, it often gives a bounded approximation. The greedy set-cover algorithm achieves a logarithmic approximation ratio, which is provably the best possible for that problem unless P equals NP. So greedy sometimes graduates from heuristic to guaranteed approximation.
How to use it
Reach for greedy first because it is simple, but verify it is correct for your problem before trusting it. If you cannot prove the greedy-choice property, treat the result as a heuristic and either bound its quality or compare it against an exact method on test instances.