--- title: Matroids & Exchange Arguments module: Greedy Algorithms moduleNumber: 7 lessonNumber: 4 order: 704 summary: | The capstone of the greedy module: _why_ and _when_ a greedy algorithm is provably optimal. We recap the two correctness templates — **greedy-stays-ahead** and the **exchange argument** — then meet the **matroid** $M=(S,\mathcal{I})$, an abstraction whose **exchange property** is the structure greedy needs. The matroid–greedy theorem says sorting by weight and taking what stays independent yields a maximum-weight basis _if and only if_ the structure is a matroid. Kruskal's MST is the canonical instance; 0/1 knapsack and TSP are the canonical failures. topics: [Greedy] sources: - book: CLRS ref: "Ch. 16 — Greedy Algorithms (§16.4 Matroids)" - book: Erickson ref: "Ch. — Matroids" - book: Skiena ref: "§ — Greedy" practice: - title: 'Maximum Number of Non-Overlapping Substrings' slug: maximum-number-of-non-overlapping-substrings difficulty: Hard - title: 'Min Cost to Connect All Points' slug: min-cost-to-connect-all-points difficulty: Medium - title: 'Maximum Performance of a Team' slug: maximum-performance-of-a-team difficulty: Hard - title: 'Course Schedule III' slug: course-schedule-iii difficulty: Hard --- Across this module greedy algorithms have succeeded (activity selection, Huffman codes, Kruskal's and Prim's spanning trees) and failed, on the 0/1 knapsack. Each success came with a _proof_: a guarantee that taking the locally best option never forecloses the global optimum. This lesson is about the proofs themselves. First we distill the two arguments every greedy correctness proof is built from. Then we ask whether a structural property _predicts_ when greedy will work, before we attempt the proof. There is one: the **matroid**. Matroid theory makes precise why Kruskal is correct and 0/1 knapsack is not, and reduces "is greedy optimal here?" to "is this structure a matroid?" ## Two templates for proving greedy optimal Every greedy correctness proof in this module is an instance of one of two patterns. They are equivalent in power but differ in mechanics. > **Remark (Greedy-stays-ahead).** Order both solutions by the steps of the algorithm. > Prove by induction on $k$ that after greedy's first $k$ choices, greedy's > partial solution is _at least as good_ as the first $k$ choices of any other > solution, by a measure that matters (finishes earliest, covers the most, > spends the least). The base case is the first choice; the inductive step shows > greedy's $k$-th choice keeps it ahead. If greedy is never behind, it cannot > lose at the end. This is the activity-selection argument: greedy's $k$-th activity finishes no later than the $k$-th activity of any valid schedule, so greedy always has at least as much room left for future activities and ends up with at least as many. > **Remark (Exchange argument).** Take _any_ optimal solution $O$ and transform it, > step by step, into the greedy solution $G$, never decreasing its quality. > Each step swaps one element of $O$ for the element greedy would have chosen, > arguing the swap is feasible and no worse. After finitely many swaps $O$ has > become $G$ with value $\ge$ its original, so $G$ is optimal too. This is the more common template: it proves the _greedy-choice property_ by showing that whatever an optimal solution does first, we may exchange it for greedy's first choice without harm.[^clrs-greedy] The two templates differ in direction: stays-ahead pushes greedy _forward_ and shows it never falls behind; exchange pulls an optimum _toward_ greedy and shows the pull never hurts. The exchange argument is the one that generalizes into a theory, because its swap step is literally an axiom of the structure we are about to define. ## Matroids A **matroid** abstracts the notion of "independence": linear independence of vectors, acyclicity of edges, freedom to add one more element without breaking a rule. > **Definition.** A **matroid** is a pair $M = (S, \mathcal{I})$ where $S$ is a > finite **ground set** and $\mathcal{I}$ is a nonempty family of subsets of $S$, > the **independent sets**, satisfying: > > 1. **(Hereditary / downward-closed)** If $B \in \mathcal{I}$ and $A \subseteq B$, > then $A \in \mathcal{I}$. Every subset of an independent set is independent. > 2. **(Exchange property)** If $A, B \in \mathcal{I}$ and $|A| < |B|$, then there > exists some $x \in B \setminus A$ such that $A \cup \{x\} \in \mathcal{I}$. The first axiom is mild; most natural notions of independence are closed under taking subsets. The **exchange property** does the work: a smaller independent set can always be grown by taking _some_ element from any larger one. It forbids getting stuck early with a maximal-but-small independent set while a much larger one exists. > **Definition.** A maximal independent set, one that cannot be extended by any > element of $S$, is a **base** of $M$. The **rank** $r(M)$ is the size of a base. A first consequence of the exchange property is that all bases have the same size. > **Claim (Bases are equicardinal).** Every base of $M$ has the same size. _Proof._ > If two bases $A, B$ had $|A| < |B|$, the exchange property would let us add an > element of $B$ to $A$, contradicting that $A$ is maximal. $\qed$ So "rank" is well-defined: every base has exactly $r(M)$ elements, exactly as every basis of a vector space has the same dimension. (Indeed, the columns of a matrix, with $\mathcal{I}$ the linearly independent subsets, form the **linear matroid**; this is where the vocabulary comes from.) $$ % caption: The exchange property — any smaller independent set $A$ can absorb some % $x \in B \setminus A$ from a larger one \begin{tikzpicture}[ every node/.style={circle, draw, minimum size=6mm, inner sep=1pt, font=\small}, >=stealth] \definecolor{acc}{HTML}{2348F2} % set A (smaller): 2 elements \node (a1) at (0,0.7) {$a$}; \node (a2) at (0,-0.7) {$b$}; \node[draw=none, font=\small\itshape] at (0,1.7) {$A$ (size 2)}; \draw[] (-0.7,-1.4) rectangle (0.7,1.4); % set B (larger): 3 elements \node (b1) at (5,1.2) {$a$}; \node (b2) at (5,0) {$c$}; \node (b3) at (5,-1.2) {$d$}; \node[draw=none, font=\small\itshape] at (5,1.9) {$B$ (size 3)}; \draw[] (4.3,-1.7) rectangle (5.7,1.6); % the new element joining A \node[draw=acc, very thick, text=acc] (anew) at (1.9,-0.7) {$c$}; \draw[->, red!75!black, very thick] (b2) .. controls (3.4,-0.4) .. (anew); \node[draw=none, text=acc, font=\footnotesize] at (2.5,-1.7) {add $c$ from $B$}; \end{tikzpicture} $$ Because $|A| < |B|$, some $x \in B \setminus A$ (here $c$) joins $A$ keeping it independent, so no maximal independent set is left stranded below the rank. ::impl{algo="matroid#is_matroid"} ## The matroid–greedy theorem A **weighted matroid** attaches a positive weight $w(x) > 0$ to each element $x \in S$, with $w(A) = \sum_{x \in A} w(x)$. The natural optimization problem: find a maximum-weight independent set. Since weights are positive and $\mathcal{I}$ is hereditary, a maximum-weight independent set is always a base. The greedy algorithm is the obvious one: sort by weight descending, add each element if it keeps the set independent. ```algorithm caption: $\textsc{Greedy}(M=(S,\mathcal I),\, w)$ — maximum-weight independent set $A \gets \varnothing$ sort $S$ into nonincreasing order by weight $w$ for each $x \in S$ in sorted order do if $A \cup \{x\} \in \mathcal{I}$ then // independence test $A \gets A \cup \{x\}$ return $A$ ``` > **Theorem (Rado–Edmonds).** If $M = (S, \mathcal{I})$ is a matroid with weight > function $w$, then $\textsc{Greedy}(M, w)$ returns a maximum-weight base of $M$. > Conversely, if $(S, \mathcal{I})$ is hereditary but _not_ a matroid, then there > is a weight function on which $\textsc{Greedy}$ fails. So greedy is optimal on a > hereditary structure **if and only if** that structure is a matroid.[^clrs-matroid] The forward direction is a clean exchange argument; it is worth seeing in full, because it is the abstract skeleton of every concrete greedy proof in this module. > **Proof (greedy is optimal on a matroid).** Let $g_1, g_2, \dots, g_r$ be greedy's > picks in the order chosen, so $w(g_1) \ge w(g_2) \ge \cdots \ge w(g_r)$, and let > $G = \{g_1, \dots, g_r\}$. Suppose for contradiction some base $O$ has > $w(O) > w(G)$. List $O$'s elements in nonincreasing weight order as > $o_1, \dots, o_r$ (both bases have size $r = r(M)$). Let $k$ be the first index > where $w(g_k) < w(o_k)$; such a $k$ exists, else $w(g_i) \ge w(o_i)$ for all $i$ > and $w(G) \ge w(O)$. > > Consider $A = \{g_1, \dots, g_{k-1}\}$ and $B = \{o_1, \dots, o_k\}$, both > independent (subsets of independent sets, by the hereditary axiom). Since > $|A| = k-1 < k = |B|$, the **exchange property** gives an element > $o_j \in B \setminus A$ with $A \cup \{o_j\} \in \mathcal{I}$. Each > $o_i \in B$ has $w(o_i) \ge w(o_k) > w(g_k)$, so $w(o_j) > w(g_k)$. > > But when greedy considered the elements in weight order, at the moment it chose > $g_k$ the set $A = \{g_1,\dots,g_{k-1}\}$ was already in hand, and > $A \cup \{o_j\}$ is independent with $w(o_j) > w(g_k)$. Greedy scans in > nonincreasing weight, so it would have reached and accepted $o_j$ **before** > $g_k$, a contradiction. Hence no such $O$ exists and $G$ is maximum-weight. > $\qed$ Laid out side by side, greedy's picks and the optimum's, both sorted by weight, make the contradiction visible. They agree on weight up to the first index $k$ where greedy falls behind ($w(g_k) < w(o_k)$). The prefix $A=\{g_1,\dots,g_{k-1}\}$ is smaller than $B=\{o_1,\dots,o_k\}$, so the exchange property yields an element $o_j\in B$ that keeps $A$ independent and is _heavier_ than $g_k$ — which greedy, scanning in weight order, must have reached and accepted before $g_k$. That is the contradiction. $$ % caption: The Rado–Edmonds exchange step. Greedy's picks $g_i$ and an allegedly better % base's picks $o_i$, both in nonincreasing weight, agree until index $k$ where % $w(g_k), very thick, red!75!black] (2.85,-0.05) to[bend right=22] (2.85,2.05); \node[red!75!black, font=\footnotesize, align=left, anchor=west] at (4.2,1.0) {$o_k = 6 > 4 = g_k$, yet the\\exchange axiom lets greedy\\add $6$ at step $k$, so its\\choice was not the greedy one.}; % bracket A: greedy's first k-1 picks (cols 1-2); label sits in the gap, clear of row O \draw[acc, thick] (-0.5,1.5) -- (-0.5,1.4) -- (1.7,1.4) -- (1.7,1.5); \node[acc, font=\footnotesize] at (0.6,1.06) {$A$: f\/irst $k$-$1$ picks}; % bracket B: O's first k picks (cols 1-3) — one more element than A \draw[acc, thick] (-0.5,-0.5) -- (-0.5,-0.6) -- (2.9,-0.6) -- (2.9,-0.5); \node[acc, font=\footnotesize] at (1.25,-1.02) {$B$: f\/irst $k$ picks (larger)}; \end{tikzpicture} $$ The single step that does all the work is "the exchange property gives an element $o_j$." That is the matroid axiom standing in for the ad-hoc swap we constructed by hand for activity selection. The converse, that a non-matroid hereditary structure has a weight function defeating greedy, is what makes the matroid the _exact_ characterization, not merely a sufficient condition: if the exchange property fails for some $A, B$, one can place weights under which greedy ends in the stranded maximal set $A$ instead of the heavier $B$. ::impl{algo="matroid#matroid_greedy"} ## Examples that are matroids **The graphic matroid.** Let $G = (V, E)$ be a graph. Take $S = E$ and let $\mathcal{I}$ be the **acyclic** edge sets, the forests of $G$. This is a matroid: a subset of a forest is a forest (hereditary), and if forests $A, B$ have $|A| < |B|$, then $B$ touches more components, so some edge of $B$ joins two trees of $A$ without creating a cycle (exchange property). The bases are the **spanning forests**; for a connected graph, the spanning trees, all of size $|V| - 1 = r(M)$. Now run $\textsc{Greedy}$ on the graphic matroid with **negated** edge weights (maximum-weight independent set becomes minimum-weight spanning tree): sort edges, add each edge that does not form a cycle. That is **Kruskal's algorithm**, exactly: the independence test "$A \cup \{e\}$ stays acyclic" is the [union-find](/algorithms/data-structures/union-find) cycle check from the [minimum spanning trees](/algorithms/graphs/minimum-spanning-trees) lesson. So Kruskal's correctness is the Rado–Edmonds theorem instantiated on the graphic matroid. $$ % caption: Acyclic edge sets form a matroid — Kruskal is matroid-greedy, taking edges by % weight and rejecting any that close a cycle \begin{tikzpicture}[ every node/.style={circle, draw, minimum size=7mm, inner sep=1pt, font=\small}, >=stealth] \definecolor{acc}{HTML}{2348F2} \node (p) at (0,1.6) {$p$}; \node (q) at (3,1.6) {$q$}; \node (r) at (0,-1) {$r$}; \node (s) at (3,-1) {$s$}; % accepted edges (in weight order 1,2,3) -> spanning tree \draw[acc, very thick] (p) -- node[draw=none, above, font=\footnotesize] {$1$} (q); \draw[acc, very thick] (p) -- node[draw=none, left, font=\footnotesize] {$2$} (r); \draw[acc, very thick] (q) -- node[draw=none, right, font=\footnotesize] {$3$} (s); % rejected edge: weight 4 would close cycle p-q-s-r-p \draw[dashed, gray] (r) -- node[draw=none, below, font=\footnotesize] {$4$ (reject)} (s); \end{tikzpicture} $$ Edges $1, 2, 3$ are accepted in weight order (blue); edge $4$ is rejected because $r$ and $s$ are already connected, so adding it would close the cycle $p\,q\,s\,r$, leaving $\mathcal{I}$. The accepted set is a base: a spanning tree. ::impl{algo="graphic_matroid"} **The uniform / partition matroid.** Even simpler: fix $k$ and let $\mathcal{I} = \{A \subseteq S : |A| \le k\}$, so every set of size at most $k$ is independent. This **uniform matroid** $U_{k,n}$ is plainly hereditary, and the exchange property is trivial (any larger set has a spare element). Greedy reduces to "pick the $k$ heaviest elements," which is obviously optimal; the matroid machinery confirms the trivial. $$ % caption: The uniform matroid $U_{3,6}$: independent means $|A|\le 3$. Greedy sorts by % weight descending and takes the first $k=3$ (blue), which is trivially the % maximum-weight base; the exchange property holds because any larger set always % has a spare element. \begin{tikzpicture}[font=\small, xscale=0.92, yscale=0.5] \definecolor{acc}{HTML}{2348F2} \foreach \i/\w/\lab/\sel in {0/5.0/9/1, 1/4.2/8/1, 2/3.4/6/1, 3/2.4/4/0, 4/1.6/3/0, 5/0.9/1/0} { \ifnum\sel=1 \fill[acc!28, draw=black, thick] (\i*1.2,0) rectangle (\i*1.2+0.9,\w); \else \fill[black, draw=black, thick] (\i*1.2,0) rectangle (\i*1.2+0.9,\w); \fi \node[font=\footnotesize] at (\i*1.2+0.45,\w+0.6) {\lab}; } \draw[acc, dashed] (3.5,-0.4) -- (3.5,6.2); \node[acc, font=\footnotesize, anchor=south] at (1.8,6.3) {keep $k=3$}; \node[font=\footnotesize, anchor=south, black] at (5.2,6.3) {reject}; \draw[->, thick] (-0.2,-0.4) -- (7.4,-0.4) node[right,font=\footnotesize]{weight order}; \end{tikzpicture} $$ The **partition matroid** generalizes it: partition $S$ into groups and allow at most $k_i$ elements from group $i$; independence is "within every group's cap." Scheduling and assignment constraints of the form "no more than $c$ of this kind" are partition-matroid constraints, which is why greedy solves so many of them. $$ % caption: A partition matroid on three groups with caps $2, 1, 2$. Independence means % respecting every group's cap; greedy takes elements in weight order, skipping % any whose group is already full (the skipped element, gray, is rejected not for % weight but for its group's cap). \begin{tikzpicture}[font=\small, xscale=0.92, yscale=0.5] \definecolor{acc}{HTML}{2348F2} % three groups, each a labeled box; picked elements blue, capped-out gray % group 1 (cap 2): take both \draw[black] (-0.2,-0.4) rectangle (2.5,4.4); \node[font=\footnotesize, anchor=south] at (1.15,4.4) {group 1, cap 2}; \fill[acc!28, draw=black] (0.1,0) rectangle (1.0,3.5); \node at (0.55,-0.9) {$9$}; \fill[acc!28, draw=black] (1.4,0) rectangle (2.3,2.8); \node at (1.85,-0.9) {$7$}; % group 2 (cap 1): take one, skip the second \draw[black] (3.0,-0.4) rectangle (5.7,4.4); \node[font=\footnotesize, anchor=south] at (4.35,4.4) {group 2, cap 1}; \fill[acc!28, draw=black] (3.3,0) rectangle (4.2,3.2); \node at (3.75,-0.9) {$8$}; \fill[black, draw=black] (4.6,0) rectangle (5.5,2.2); \node[black] at (5.05,-0.9) {$5$}; \node[black, font=\footnotesize] at (5.05,3.1) {skip}; % group 3 (cap 2): take both \draw[black] (6.2,-0.4) rectangle (8.9,4.4); \node[font=\footnotesize, anchor=south] at (7.55,4.4) {group 3, cap 2}; \fill[acc!28, draw=black] (6.5,0) rectangle (7.4,3.0); \node at (6.95,-0.9) {$6$}; \fill[acc!28, draw=black] (7.8,0) rectangle (8.7,1.6); \node at (8.25,-0.9) {$3$}; \end{tikzpicture} $$ Greedy walks the elements in weight order and admits each unless its group is already at capacity. Here the weight-$5$ element is skipped even though heavier elements elsewhere were still being accepted — not because of its weight but because group 2's single slot is already spent. That per-group cap is the independence rule, and the exchange property holds because a set below some cap can always borrow an element from any group where a larger set has room. ::impl{algo="uniform_matroid"} **Beyond greedy: matroid intersection.** A single matroid yields to greedy; the common independent sets of _two_ matroids over the same ground set do not, in general. Still, **matroid intersection** solves the maximum-weight common independent set in polynomial time by augmenting-path methods (bipartite matching is a special case). The intersection of _three_ matroids is already NP-hard. So the matroid is the precise frontier of "greedy works"; one step beyond it you need heavier machinery. ## Why 0/1 knapsack and TSP are _not_ matroids The theorem cuts both ways, and it explains the failures we have already seen. **0/1 knapsack.** Recall from the [greedy method](/algorithms/greedy/the-greedy-method) lesson that greedy fails on the 0/1 knapsack, and from the [knapsack DP](/algorithms/dynamic-programming/knapsack) lesson that it needs dynamic programming. The reason, in matroid language: let $S$ be the items and call a set "independent" if its total _weight_ fits in capacity $W$. This is hereditary: drop items and it still fits. But the **exchange property fails**. Take capacity $W = 8$ and item sizes giving the independent sets $\{7\}$ and $\{4, 4\}$. Both fit, and $|\{4,4\}| = 2 > 1 = |\{7\}|$, yet _no_ element of $\{4,4\}$ can join $\{7\}$, since $7 + 4 = 11 > 8$. The smaller independent set is stranded: it cannot grow toward the larger one, which is the exact pattern the exchange property forbids. $$ % caption: 0/1 knapsack is not a matroid ($W=8$). The independent set $\{7\}$ and the % larger $\{4,4\}$ both fit, yet adding either $4$ to $\{7\}$ gives $11>8$. No % element of the larger set can grow the smaller, so the exchange property fails. \begin{tikzpicture}[font=\small, yscale=0.5, xscale=0.9] \definecolor{acc}{HTML}{2348F2} \draw[dashed, black] (-0.3,8) -- (8.6,8); \node[font=\footnotesize, anchor=west] at (8.7,8) {$W=8$}; \draw[thick] (0,0) rectangle (1.6,8); \fill[acc!22, draw=black] (0,0) rectangle (1.6,7); \node at (0.8,3.5) {$7$}; \node[below, font=\footnotesize] at (0.8,0) {one item: $7$}; \draw[thick] (3,0) rectangle (4.6,8); \fill[acc!22, draw=black] (3,0) rectangle (4.6,4); \fill[acc!12, draw=black] (3,4) rectangle (4.6,8); \node at (3.8,2) {$4$}; \node at (3.8,6) {$4$}; \node[below, font=\footnotesize] at (3.8,0) {two items: $4+4$}; \draw[thick] (6.2,0) rectangle (7.8,11.2); \fill[acc!22, draw=black] (6.2,0) rectangle (7.8,7); \fill[red!25, draw=black] (6.2,7) rectangle (7.8,11); \node at (7,3.5) {$7$}; \node at (7,9) {$4$}; \node[red, below, font=\footnotesize, align=center] at (7,0) {$7{+}4{=}11>8$\\ exchange fails}; \end{tikzpicture} $$ The exchange property is violated; the structure is not a matroid; and by Rado–Edmonds _some_ weighting must defeat greedy, recovering the value/density counterexample from the greedy-method lesson. **Traveling salesman.** For the TSP, let $\mathcal{I}$ be the edge sets that extend to a Hamiltonian tour (or the partial-tour fragments greedy builds). This is not even reliably hereditary, and the exchange property fails badly: a cheap partial path can be a dead end that no edge of a longer, valid fragment can extend without revisiting a vertex or exceeding degree $2$. There is no matroid, so no weighting guarantee, and indeed nearest-neighbor greedy can be made arbitrarily bad. The independence structure simply is not a matroid (and TSP is NP-hard regardless). The pattern is uniform. When greedy is provably optimal, you can almost always exhibit a matroid behind it. When greedy fails, the exchange property is the axiom that breaks. ## Greedoids, submodularity, and the reach of "greedy works" The matroid is the exact frontier for the _classical_ greedy algorithm, but the question "when is a greedy-style method provably good?" has answers well past it, developed since Rado and Edmonds. **Matroid intersection and matroid union.** As noted, the common independent sets of _two_ matroids over one ground set no longer yield to plain greedy, yet **matroid intersection** finds a maximum-weight common independent set in polynomial time by augmenting paths, with bipartite matching and many assignment problems as special cases; the intersection of _three_ matroids is NP-hard.[^edmonds-int] So the tractable boundary is precisely _two_ matroids. **Greedoids.** Relaxing the hereditary axiom to an _accessibility_ axiom gives the **greedoid** (Korte & Lovász, 1981), a structure broad enough to include the search order of breadth-first and depth-first trees and Dijkstra/Prim shortest-path growth, all of which are greedy but not matroid-greedy.[^greedoid] The greedoid explains why those algorithms, too, admit clean exchange-style proofs. **Submodularity: the modern generalization.** The deepest extension replaces "sets that stay independent" with **submodular** objective functions — set functions with _diminishing returns_, where adding an element to a smaller set helps at least as much as adding it to a larger one. Nemhauser, Wolsey, and Fisher (1978) proved that for maximizing a monotone submodular function under a cardinality constraint, the greedy rule (repeatedly add the element of largest marginal gain) is a $(1 - 1/e) \approx 0.632$ approximation, and Feige (1998) showed no polynomial-time algorithm beats it unless $\mathrm{P} = \mathrm{NP}$.[^nwf] Submodular greedy now underlies influence maximization, sensor placement, feature and data selection, and document summarization — a direct descendant of the exchange argument, generalized from _independence_ to _diminishing returns_. $$ % caption: Diminishing returns (submodularity): the marginal gain of adding element $x$ to % a set shrinks as the set grows. Greedy repeatedly takes the largest marginal gain; % for monotone submodular objectives this is a $1-1/e$ approximation. \begin{tikzpicture}[font=\small, >=stealth, xscale=0.9, yscale=0.6] \definecolor{acc}{HTML}{2348F2} \draw[->, thick] (0,0) -- (7.2,0) node[right, font=\footnotesize] {set size}; \draw[->, thick] (0,0) -- (0,4.0) node[above, font=\footnotesize] {gain of adding $x$}; % decreasing bars: marginal gains shrink \foreach \i/\h in {0/3.4, 1/2.4, 2/1.7, 3/1.1, 4/0.7, 5/0.4} { \fill[acc!22, draw=acc, thick] (\i*1.1+0.35,0) rectangle (\i*1.1+1.0,\h); } \node[acc, font=\footnotesize, anchor=west] at (3.2,3.2) {marginal gain of $x$ falls}; \end{tikzpicture} $$ ## Takeaways - Every greedy correctness proof is a **greedy-stays-ahead** induction (greedy's $k$-th partial solution is never behind any rival's) or an **exchange argument** (transform any optimum into the greedy solution without loss). They are equivalent in power; exchange is the one that abstracts into a theory. - A **matroid** $M = (S, \mathcal{I})$ is a ground set plus a **hereditary** family of **independent** sets satisfying the **exchange property**: any smaller independent set can absorb some element of any larger one. Maximal independent sets are **bases**; they all share size $r(M)$, the **rank**. - **Rado–Edmonds theorem:** on a weighted matroid, sorting by weight and greedily keeping independence yields a **maximum-weight base**, and greedy is optimal on a hereditary structure _iff_ it is a matroid. The proof's one nontrivial step rests on the exchange axiom. - The **graphic matroid** (acyclic edge sets) makes **Kruskal's MST** an exact instance of matroid-greedy; the **uniform / partition matroid** captures "at most $k$ of each kind" constraints. **Matroid intersection** is the polynomial-time frontier just beyond single-matroid greedy. - **0/1 knapsack** and **TSP** are _not_ matroids (the exchange property fails), which is the structural reason greedy fails on them and dynamic programming or exact search is required instead. [^clrs-greedy]: **CLRS**, Ch. 16 — Greedy Algorithms (§16.2): the greedy-choice property and optimal substructure, proved by exchanging an optimal solution's first choice for greedy's. [^clrs-matroid]: **CLRS**, Ch. 16 — Greedy Algorithms (§16.4): the Rado–Edmonds theorem — greedy returns a maximum-weight independent set exactly when the structure is a matroid; the proof rests on the exchange property. [^edmonds-int]: **Edmonds, J.** (1970), "Submodular functions, matroids, and certain polyhedra," in _Combinatorial Structures and Their Applications_, 69–87 — the matroid-intersection theorem; two matroids are polynomial, three are NP-hard. [^greedoid]: **Korte, B. & Lovász, L.** (1981), "Mathematical structures underlying greedy algorithms," in _Fundamentals of Computation Theory_, LNCS 117, 205–209 — greedoids, relaxing heredity to accessibility so that BFS/DFS/Dijkstra-style growth becomes greedy-provable. [^nwf]: **Nemhauser, G. L., Wolsey, L. A. & Fisher, M. L.** (1978), "An analysis of approximations for maximizing submodular set functions—I," _Mathematical Programming_ 14, 265–294 — the greedy $(1-1/e)$ bound for monotone submodular maximization; matched by the hardness of **Feige, U.** (1998), "A threshold of $\ln n$ for approximating set cover," _JACM_ 45(4), 634–652.