Greedy Algorithms & Matroids
Greedy Algorithms & Matroids
Greedy algorithms build a solution incrementally, always choosing the locally optimal option. They are fast but not always optimal — correctness requires proof. Matroids are the algebraic structure that characterizes exactly when greedy algorithms yield global optima for optimization problems.
Greedy & Matroid Theory
A matroid $M=(S,\mathcal{I})$: $S$ is the ground set; $\mathcal{I}\subseteq 2^S$ are independent sets. Matroid axioms: (i) $\emptyset\in\mathcal{I}$; (ii) $A\in\mathcal{I},B\subseteq A\Rightarrow B\in\mathcal{I}$ (hereditary); (iii) $A,B\in\mathcal{I},|A|>|B|\Rightarrow\exists x\in A\setminus B$ with $B\cup\{x\}\in\mathcal{I}$ (augmentation). Greedy theorem: for a weighted matroid, the greedy algorithm (add highest-weight element that preserves independence) finds the maximum-weight basis.
Kruskal's as Greedy on Graphic Matroid
The graphic matroid of $G$: $S=E(G)$, $\mathcal{I}=\{$forests$\}$ (acyclic subsets). Kruskal's algorithm: sort edges by weight, add edge if it doesn't form a cycle. By the greedy theorem applied to the graphic matroid, this finds the minimum spanning tree (weight-negated maximum basis). Proof of matroid axioms: hereditary obvious; augmentation by circuit property of forests.
Example 1
Prove Huffman coding is a greedy algorithm that produces an optimal prefix-free code.
Solution: Huffman's algorithm: repeatedly merge the two lowest-frequency symbols. Correctness proof by exchange argument: suppose an optimal code $T^*$ doesn't place the two least-frequent symbols as siblings at the deepest level; swapping to the Huffman structure cannot increase cost. Induction: after merging, optimal sub-code for combined symbol implies overall optimality.
Example 2
Show Dijkstra's algorithm is a greedy algorithm. Why doesn't it work with negative edges?
Solution: Greedy choice: always extract the vertex $u$ with minimum current distance $d[u]$. Correctness: when $u$ is extracted, $d[u]$ is the true shortest distance (by non-negative weights: no future relaxation can improve $d[u]$ since all future paths through unvisited vertices have $d\geq d[u]$). Negative edges: a later vertex might have a shorter path via a negative edge, contradicting the greedy finality.
Practice
- Prove the greedy algorithm finds a maximum-weight independent set in any matroid.
- Show the interval scheduling problem (maximize non-overlapping intervals) is solved optimally by earliest-deadline-first greedy.
- Give an example where a greedy algorithm fails: construct a greedy algorithm for coin change that fails with denominations $\{1,3,4\}$ and amount 6.
- Describe the partition matroid and show that scheduling jobs with deadlines reduces to matroid optimization.
Show Answer Key
1. Matroid: $(E, \mathcal{I})$ with hereditary and exchange properties. Greedy: sort elements by decreasing weight, add each element if the result remains independent. Proof: by exchange property, if the greedy set $G$ differs from optimal $O$, there exists $e\in O\setminus G$ that can replace some $g\in G\setminus O$ with $w(e)\leq w(g)$ (since greedy chose $g$ first). Contradiction with $O$ being heavier. ✓
2. Sort intervals by finish time. Greedily select the earliest-finishing interval that doesn't overlap with the last selected. Proof: exchange argument — if optimal solution $O$ differs, its first differing interval $o_i$ finishes later than greedy's $g_i$. Replacing $o_i$ with $g_i$ can't cause conflicts (earlier finish), and the remaining schedule is at least as good. By induction, greedy matches or beats optimal. ✓
3. Greedy with $\{1,3,4\}$ for amount 6: picks $4+1+1 = 3$ coins. Optimal: $3+3 = 2$ coins. The greedy fails because the denomination set doesn't have the greedy property (not a matroid). Greedy works for canonical systems (e.g., US coins) but not all denomination sets.
4. Partition matroid: ground set $E$ partitioned into groups $E_1,\ldots,E_k$; a set $I$ is independent if $|I\cap E_i|\leq u_i$ for each $i$. Job scheduling with deadlines: jobs are elements, group $E_t$ = jobs with deadline $\leq t$, $u_t = t$. An independent set = a feasible schedule. Maximizing weighted independent set in this matroid = maximizing total value of jobs completed by their deadlines. Greedy by decreasing weight solves it optimally.