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:

Easy to devise (from an initial analysis of the problem)
Easy to determine time complexity (usually sort + some constant time processing)
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:

Focus on the differences. Typically, you can isolate a simple example of this difference, such as one of the following:
- there is an element of O that is not in A and an element of A that is not in O, or
- there are 2 consecutive elements in O in a different order than they are in A (i.e. there is an inversion).
Exchange to show that going from \(\sigma^*\) to \(\sigma\) will create a more optimal solution.
Arrive at the contradiction. Hence, the optimal solution cannot be better than the greedy solution.

However, it is easy to trip up with exchange arguments. Here are some common pitfalls to avoid:

Be careful about using proofs by contradiction starting with the assumption \(\sigma\neq\sigma^*\). Just because your greedy solution is not equal to the selected optimal solution does not mean that greedy is not optimal – there could be many optimal solutions, and your greedy one just isn’t the optimal solution you selected. So assuming \(\sigma\neq\sigma^*\) may not get you any contradiction at all, even if greedy works.
You need to argue why the 2 elements you’re swapping even exist out of order, or exist in \(\sigma^*\) but not in \(\sigma\), etc.
Remember you need to argue that multiple swaps can get you from your selected solution to greedy, as one single swap will usually not suffice.
Make sure that any step you make (and not just the first one) doesn’t hurt the solution quality.

A simple illustrative case is the scheduling problem. The greedy approach picks the task that has the earliest deadline.

Suppose we have an optimal schedule (\(\sigma^*\)) that is different from the EDF schedule (\(\sigma\)).

Look at the first position where (\(\sigma^*\)) and (\(\sigma\)) differ.
At this position, (\(\sigma^*\)) schedules a job (\(J_i\)) with a later deadline before a job (\(J_j\)) with an earlier deadline.
This creates an inversion: two consecutive jobs are in the wrong order relative to EDF.

Now, swap (\(J_i\)) and (\(J_j\)) in (\(\sigma^*\)).

After the swap, (\(J_j\)) (earlier deadline) comes before (\(J_i\)).
This exchange does not increase the maximum lateness:
- (\(J_j\)) finishes earlier, which can only reduce its lateness.
- (\(J_i\)) finishes later, but since its deadline is later than (\(J_j\))’s, its lateness does not increase beyond what it was before.
The swap reduces the number of inversions.

By repeatedly applying this exchange, we can eliminate all inversions.

Eventually, (\(\sigma^*\)) transforms into (\(\sigma\)), the EDF schedule.
Since (\(\sigma^*\)) was assumed optimal, and we can transform it into EDF without worsening maximum lateness, EDF must also be optimal.
Contradiction: there cannot exist a schedule strictly better than EDF.

Direct Proof

An exhcnage argument can also be presented as a direct proof where you assume that the greedy solution \(\sigma_G\) is better than an arbitrary solution \(\sigma\). Then, we can use the principle of an exchange argument to show that we can convert any solution \(\sigma\) to the greedy solution \(\sigma_G\) by performing exchanges that make the solution more optimal. Since the greedy solution is an improvement over every arbitrary solution, it can be shown to be the best solution.

Justifying Greedy

Here is how to show that a problem can be solved with a greedy algorithm:

Cast the problem where we have to make a greedy choice. This leaves us with just one sub problem to solve.
Prove (usually using an exchange argument) that there is always an optimal solution to the original problem that makes the greedy choice.
Use optimal substructure (usually using proof by contradiction) to show that we can combine an optimal solution to the sub problem with the greedy choice to get an optimal solution to the original problem.