Greedy Algorithms8 sections · 316 units
Open in Course

Vocabulary - Exchange Argument

Swap to improve

The exchange argument proves greedy works by transformation. The idea:

1.1. Assume there is some optimal solution OPT that differs from greedy solution G.

2.2. Find a specific difference between OPT and G.

3.3. Show you can swap OPT's choice for G's choice without making OPT worse.

4.4. Repeat until OPT becomes G. If you can always swap without losing quality, then G is at least as good as any OPT. Therefore G is optimal. The key is showing each swap maintains or improves quality.