Greedy Algorithms

Why This Matters

Greedy algorithms are often the first approach you try for an optimization problem. They are fast, easy to implement, and sometimes provably optimal. The hard part is knowing when they work. A greedy algorithm that looks correct can silently produce suboptimal solutions if the problem lacks the right structure.

Mental Model

At each step, pick the option that looks best right now without worrying about future consequences. If the problem has the right combinatorial structure, this myopic strategy assembles a globally optimal solution.

The key insight: greedy works when you can always extend a partial solution by the locally best choice without painting yourself into a corner.

Core Definitions

Definition

Greedy Algorithm

An algorithm that builds a solution incrementally, at each step choosing the element that maximizes (or minimizes) some local criterion, and never revising past choices.

Definition

Matroid

A matroid is a pair $(E, \mathcal{I})$ where $E$ is a finite ground set and $\mathcal{I} \subseteq 2^E$ is a family of independent sets satisfying: (1) $\emptyset \in \mathcal{I}$, (2) if $A \subseteq B \in \mathcal{I}$ then $A \in \mathcal{I}$ (hereditary), (3) if $A, B \in \mathcal{I}$ and $|A| < |B|$, then there exists $e \in B \setminus A$ such that $A \cup \{e\} \in \mathcal{I}$ (exchange property).

Main Theorems

Theorem

Greedy is Optimal on Matroids

Statement

Let $(E, \mathcal{I})$ be a matroid with a weight function $w: E \to \mathbb{R}_{\geq 0}$. The greedy algorithm that iteratively adds the maximum-weight element maintaining independence produces a maximum-weight independent set.

Intuition

The exchange property guarantees that if the greedy solution were suboptimal, you could swap an element from a better solution into the greedy solution without breaking independence, contradicting the greedy choice.

Proof Sketch

Suppose greedy produces $G = \{g_1, \ldots, g_k\}$ sorted by weight and an optimal solution is $O = \{o_1, \ldots, o_k\}$. If $w(g_i) < w(o_i)$ for some first index $i$, the exchange property lets us replace $g_i$ with some element from $O$ of weight at least $w(o_i)$. But greedy chose $g_i$ as the heaviest feasible element, a contradiction.

Why It Matters

This theorem tells you exactly when greedy works: when the feasible sets form a matroid. Graphic matroids give you Kruskal's algorithm. Partition matroids give you scheduling problems. Recognizing matroid structure is the principled way to justify greedy correctness.

Failure Mode

When the independence structure is not a matroid, greedy can fail badly. The 0/1 knapsack problem is the classic example: the feasible sets do not form a matroid, and greedy by value-to-weight ratio can miss the optimal solution entirely.

Canonical Examples

Example

Activity Selection (Interval Scheduling)

Given $n$ activities with start and finish times, select the maximum number of non-overlapping activities. Greedy rule: always pick the activity that finishes earliest. This works because the set of non-overlapping subsets forms a matroid-like structure (technically an interval scheduling matroid). Time complexity: $O(n \log n)$ for sorting.

Example

Kruskal's MST Algorithm

To find a minimum spanning tree, sort edges by weight and add each edge if it does not create a cycle. The acyclic subsets of a graph form a graphic matroid, so the matroid greedy theorem guarantees optimality. Time complexity: $O(m \log m)$ with union-find.

Example

Huffman Coding

Build an optimal prefix-free code by repeatedly merging the two lowest-frequency symbols. The greedy choice (merge cheapest pair) is justified by an exchange argument: any optimal tree can be rearranged so the two rarest symbols are siblings at the deepest level.

Example

Fractional Knapsack

Given items with values and weights, and a capacity $W$, maximize total value. Greedy rule: sort by value-to-weight ratio and take as much of each item as fits. Because you can take fractions, this greedy strategy is provably optimal. Time complexity: $O(n \log n)$.

Common Confusions

Watch Out

Fractional knapsack is greedy-optimal but 0/1 knapsack is NOT

In the fractional knapsack, you can take any fraction of an item, so the greedy strategy of maximizing value-to-weight ratio works perfectly. In the 0/1 knapsack, you must take an item entirely or not at all. This all-or-nothing constraint breaks the exchange property. Consider: items with values (60, 100, 120) and weights (10, 20, 30) with capacity 50. Greedy by ratio takes items 1 and 2 (value 160), but optimal is items 2 and 3 (value 220). Use dynamic programming for 0/1 knapsack instead.

Watch Out

Proving greedy correct requires a formal argument

It is not enough to say a greedy algorithm looks right. You need either: (1) a matroid structure argument, (2) an exchange argument showing you can transform any optimal solution to match greedy choices, or (3) a greedy-stays-ahead argument showing the greedy solution dominates any alternative at every step.

Proof Ideas and Templates Used

The exchange argument is the primary proof technique:

1. Assume an optimal solution $O$ differs from the greedy solution $G$.
2. Find the first point of divergence.
3. Show you can modify $O$ to agree with $G$ at that point without worsening the objective.
4. By induction, $O$ can be transformed into $G$ without loss of quality.

Summary

• Greedy works when the problem has matroid structure or admits an exchange argument
• Always sort by the right criterion (finish time, weight, ratio, frequency)
• Greedy for fractional knapsack, DP for 0/1 knapsack
• Proving greedy correct is as important as designing the algorithm
• Time complexity is usually dominated by the initial sort: $O(n \log n)$

Exercises

ExerciseCore

Problem

You have $n$ jobs each taking unit time, with deadlines $d_i$ and profits $p_i$. You can schedule at most one job per time slot. Describe a greedy algorithm to maximize total profit from jobs completed by their deadlines.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Give a concrete example showing that greedy by value-to-weight ratio fails for the 0/1 knapsack problem. What is the approximation ratio of this greedy in the worst case?

Hint

Reveal Solution

References

Canonical:

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), Chapters 15-16
• Oxley, Matroid Theory (2011), Chapter 1

Accessible:

• Kleinberg & Tardos, Algorithm Design, Chapter 4

• Hastie, Tibshirani, Friedman, The Elements of Statistical Learning (2009)

Next Topics

• Dynamic programming: the paradigm for problems where greedy fails