Greedy Algorithms8 sections · 316 units
Open in Course

Vocabulary - Stays Ahead Argument

Always leading

The stays ahead argument proves greedy works by showing it is never behind. The idea: define a measure of "progress" at each step. Prove by induction that greedy's progress is always at least as good as any other solution's progress.

If greedy is never behind at any step, it must be optimal at the end. This technique is sometimes easier than exchange, especially when the comparison between solutions is natural. The key is choosing the right measure of progress.