Matroids & the Greedy Algorithm

The exchange axiom is exactly when greedy is optimal.

The idea

The greedy algorithm builds a heavy independent set one element at a time. It is fast, and it never reconsiders a choice. On some structures it returns a maximum-weight independent set for every choice of weights; on others it does not, and the axiom below separates the two cases exactly.

The setting is an independence system: a ground set $E$ together with a family $\mathcal{F}$ of subsets called independent, closed under taking subsets, so every subset of an independent set is again independent. Such a system is a matroid when it also satisfies the exchange axiom: whenever $X, Y \in \mathcal{F}$ with $|X| < |Y|$, some element $e \in Y \setminus X$ has $X \cup \{e\} \in \mathcal{F}$. In words, a smaller independent set can always borrow an element from a larger one and stay independent.

Algorithm.

Algorithm: Greedy Input: an independence system (E, F) and a weight for each element of E Output: an independent set S assembled from heavy elements 1. sort the elements of E by decreasing weight 2. S = ∅ // S stays independent throughout the run 3. take the next element e in sorted order if S ∪ {e} is independent, S = S ∪ {e} otherwise discard e, never to be reconsidered 4. if elements remain, go to step 3 5. return S

The greedy theorem. The greedy algorithm returns a maximum-weight independent set for every weight function if and only if $(E, \mathcal{F})$ is a matroid. The equivalence runs in both directions: on a matroid, greedy is optimal no matter what the weights are, and on any independence system that is not a matroid, some weight function makes greedy return a set of less than maximum weight.

Ways to work on it

• Walkthrough. Independence systems, the exchange axiom, and why it makes greedy optimal.
• Practice. Apply the exchange axiom in a uniform matroid.
• Hardest. Run greedy on the graphic matroid and pin down when it fails.

Not sure where to start? Take the ten-question placement test.