The Greedy paradigm is a general approach to problem solving. It involves making a series of myopic and irrevocable decisions which lead to the optimal solution.

This breaks down solving the problem into solving one problem repeatedly.

Thus we can solve the problem iteratively.

This makes it a powerful problem solving approach but the problem is that for most problems, the greedy approach does not produce the right answer.

Hence, proofs are core to the greedy paradigm: we need to be able to prove that the greedy approach leads to the correct answer.

Greedy algorithms usually share the following characteristics:

1. Easy to devise (from an initial analysis of the problem)
2. Easy to determine time complexity (usually sort + some constant time processing)
3. Hard to prove correctness

If a greedy approach fails, then we have to turn to the other methods, namely divide and conquer or (at the worst-case) brute-force search of the solution space

Approach to proofs

The core analytic idea in the greedy paradigm is the idea of an optimal substructure:

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.

Exchange Arguments

The other important idea for greedy algorithms is the exchange argument.

The goal of the exchange argument is to show that of the multiple optimal solutions, there exists one optimal solution that is reached by the greedy approach (i.e. greedy algorithms lead to an optimal solution).

There are multiple ways to write out an exchange argument. Here, we present a popular approach to an exchange argument, which gives an idea of how an exchange argument may be structured.

Using contradiction

The first approach to exchange arguments uses proof by contradiction. The assumption that we make (which we then try to contradict) is that there exists an optimal solution $\sigma^*$ which performs better than the greedy solution $\sigma$.

The end result we are aiming for is to show that the greedy solution performs better than the assumed optimal solution $\sigma^*$, leading to a contradiction.

Here is how we set about writing out an exchange argument to follow this line of reasoning: