Greedy Algorithms

A greedy algorithm is an algorithmic approach that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. It iteratively makes one greedy choice after another, reducing the given problem into a smaller one. At each step, it makes a decision that seems to be the best at that moment. So, it works well when the locally optimal choice is also the globally optimal one.

Usually, a greedy algorithm consists of 2 steps

1. Sorting the provided data according to a chosen heuristic, this heuristic is differnt for each problem.
2. Create a solution using the sorted array and some extra heuristics.

It can be proven that they always find the optimal solution To prove the optimality of greedy algorithms, there are two methods:

Greedy Stays Ahead

Greedy stays ahead is a technique to prove that a solution generated by a greedy algorithm is optimal. A general step by step approach to prove an algorithm’s correctness can be summarized as such.

1. Show that a greedy algorithm always makes locally optimal solutions.
2. Prove that if we choose any other local solution, we cannot reach the globally optimal solution.
3. Use mathematical induction to prove that greedy always stays ahead of any other solution

A General Skeleton

Let $S$ be the set of choices generated by our greedy solution and let $\mathcal{O}$ be the optimal set of choices. Refer to each element in the solutions as $s_1,s_2,...,s_i$ and $o_1,o_2,...,o_j$ respectively. Let $g(n_c)$ be a function that measures the optimality of a set of choices up $n_c$. We will use induction to prove that $g(s_r)\le g(o_k)$ (or the other way around, depends on whether we want to maximize or not) for any two arbitrary integers $r$ and $k$ such that $r\le k$.

• Base Case: Show that $g(s_0)=g(o_0)$.
• Inductive Hypothesis: Assume that $g(s_r)\le g(o_k)$ holds for any arbitrary $r$ and $k$
• Inductive Step: Now prove that $g(s_{r+1})\le g(o_{k+1})$ assuming that the inductive hypothesis holds. This part requires some math. Usually, we try to prove that the reverse($g(s_{r+1})>g(o_{k+1})$) and derive a contradiction with the definition of the greedy algorithm from there.

Therefore we have proven that $g(s_{r+1})\le g(o_{k+1})$ holds if the inductive hypothesis holds. This, combined with the base case forms the proof that greedy always stays ahead.

Exchange Argument

The exchange argument is a proof method used to prove the optimality of Greedy Algorithms. The proof is based on the idea that given an optimal solution with inversions, commpared to the the greedy solution, fixing those inversions brings the optimal solution closer to the greedy solution whilst preserving optimality.

WARNING

For two elements in the wrong order compared to the greedy solution to be considered an inversion, they need to be next to each other.

A basic skeleton

1. Let the solution produced by our greedy algorithm be $S$
2. Let $\mathcal{O}$ be the optimal solution with the least amount of inversions.
3. Assume that greedy does not produce optimal solutions.
4. Define what an inversion is, show that by definition $S$ cannot have any inversions.
5. From here, we have two cases:
   1. $\mathcal{O}$ does not have any inversions, this immediately contradicts with our statement at step 3.
   2. $\mathcal{O}$ has at least one inversion. This impliest that there two points $(o_i,o_{i+1})$ that are inverted. It is best to start this part with “Consider a solution…”
      1. Show that swapping the inverted elements preserves the optimality of the solution.
      2. Show that swapping the two points removes the inversion
      3. Show that swapping the two points does not introduce any new inversions.
      4. State that this creates a new solution ${\mathcal{O}}^{\prime }$ that is still optimal and yet has less number of inversions than $\mathcal{O}$.
      5. This means $\mathcal{O}$ is not the optimal solution with the least number of inversions, contradicting step 2.
      6. By reducing the number of inversions we brough ${\mathcal{O}}^{\prime }$ closer to $S$ while preserving the optimality. This contradicts with step 3.
      7. Thus, the solution $S$ is optimal