For any given problem, let be the set of possible solutions, and be a function that maps a solution to a measure of how “good” it is. We have .
Usually, we also have a set of constraints that we must respect, where . The optimal solution will belong in , and correspond to the maximum or minimum value that can return from this subset.
There are many approaches to optimization problems, like DP and Greedy algorithms.
Exchange argument
Let be the solution produced by our . We want to prove this is the optimal solution. The idea is that we pretend to have another optimal solution and exchange it with a different that is one more unit closer to our greedy solution.
We can have multiple optimal solutions in a solution space, and if we keep exchanging equivalent solutions, we can get to our greedy solution.
More formally, for each greedy algorithm we can prove the following lemma: there exists a such that agrees with on decisions. We want to show that there exists another optimal solution such that it agrees with on decisions.
We prove using induction that this holds true whenever we increment . Eventually we’ll reach the in our algorithm and that would prove our greedy solution .
If there only exists one unique, optimal solution, then and we will see that in our analysis.