Exchange Argument Structure

Here is the formal structure of an exchange argument: Claim: The greedy solution G is optimal. Proof: Let OPT be any optimal solution. I will show OPT can be transformed into G without losing optimality. $1.$ Find the first position $i$ where OPT and G differ.

$2.$ Let G choose item $g$ and OPT choose item $o$ at position $i$.

$3.$ Construct a new solution OPT' by swapping $o$ for $g$ in OPT.

$4.$ Show that OPT' is valid and has quality >= OPT.

$5.$ OPT' agrees with G on one more position. Repeat until OPT' = G. Since G can be reached from any OPT without losing quality, G is optimal.