Greedy Algorithms and Matroids

When Is Greed Optimal?

A greedy algorithm makes the locally best choice at each step, never revisiting past decisions. Simple and fast — but not always optimal. The greedy algorithm for the knapsack problem does not produce an optimum. Kruskal’s greedy algorithm for MST — produces an optimum. Why? The answer is the matroid structure of the problem. Matroids are an abstract algebraic structure, and for them, greed is always optimal. This is one of the deepest and most beautiful results in combinatorial optimization.

Greedy Algorithm for MST: Proof

Kruskal’s Algorithm: sort the edges by weight. Greedily add the minimum edge that does not create a cycle.

Cut Lemma: for any cut (S, V∖S), the minimum edge crossing the cut is included in the MST.

Proof: let $e^$ be the minimum edge crossing the cut, and let $T$ be an MST not containing $e^$. Add $e^$ to $T$ → a cycle is formed, which crosses the cut at least in one other edge $e'$. Since $e^$ is minimal in the cut: $w(e^) \leq w(e')$. Replace $e'$ with $e^$ in $T$ → new tree $T'$, with $w(T') \leq w(T)$. But $T$ is an MST → $w(T') = w(T)$, and $e^*$ is included in the MST. ✓

Matroid: Definition

Matroid $M = (E, I)$: $E$ — the “elements”, $I \subseteq 2^E$ — the “independent” sets. Axioms:

I1 (non-empty): $\varnothing \in I$.

I2 (hereditary): if $Y \in I$ and $X \subseteq Y$, then $X \in I$ (a subset of an independent set is independent).

I3 (exchange): if $X, Y \in I$ and $|X| < |Y|$, then there exists $e \in Y \setminus X$ such that $X \cup {e} \in I$.

Axiom I3 is key! It means you can always “grow”: a smaller independent set can be extended by an element from the larger.

Basis of a matroid: a maximal independent set. By I3 all bases have the same size (the rank of the matroid).

Examples of Matroids

Graphic matroid (cycle matroid): $E$ = edges of graph $G$, $I$ = acyclic subgraphs (forests). Basis = spanning tree (MST!).

Checking the axioms: $\varnothing$ is a forest ✓. A subgraph of a forest is a forest ✓. Exchange: if $|F_1| < |F_2|$ for forests, then $F_2$ has more connected components → there exists an edge in $F_2$ connecting different components of $F_1$ → add it to $F_1$ without forming a cycle ✓.

Linear matroid: $E$ = columns of matrix $A$ over field $F$, $I$ = linearly independent subsets of columns. The rank of the matroid equals the rank of the matrix.

Partition matroid: $E$ is partitioned into groups $E_1, ..., E_k$. $I$ = sets with no more than 1 element from each $E_i$. Used to represent schedules.

Uniform matroid $U_{k n}$: $I$ = all subsets of $E$ of size $\leq k$. This is a “$k$-sparse” matroid.

Rado-Edmonds Theorem

Theorem: the greedy algorithm is optimal for the maximum-weight independent set problem if and only if $(E, I)$ is a matroid.

Greedy algorithm: sort the elements in order of decreasing weight. Add the next element if after adding the set remains independent.

Proof “⇐” (matroid → greed is optimal): induction by the size of the set. At each step, the maximal element must be in some optimum (otherwise, replacement is possible via the exchange axiom).

Proof “⇒” (greed is optimal → matroid): if I3 is violated, construct weights for which greed gives a non-optimal solution.

Corollaries

MST: graphic matroid → Kruskal’s algorithm is optimal ✓.

Assignment problem: bipartite graph $G$, need to pick $k$ edges, none incident to the same vertex (= matching of size $k$). This is the intersection of two partition matroids! → polynomially solvable (Edmonds’ algorithm).

Huffman’s problem: optimal prefix code for compression. Huffman’s greedy algorithm is optimal — the structure is matroidal.

Intersection of Matroids

Problem: find the largest independent set $I \in I_1 \cap I_2$ (intersection of two matroids).

Algorithm: $O(r^2 \cdot T_{oracle})$, where $r$ is the rank, $T_{oracle}$ is the time to check independence. Polynomial!

Intersection of 3 matroids: NP-hard. This is the boundary of polynomial-time solvability.

Examples:

• Maximum matching in a bipartite graph = intersection of two partition matroids
• Coloring a bipartite graph = intersection of two matroids (color assignment)

Full Example: Greedy Algorithm for Weighted Matroid

Problem: Graph $G$ with 5 vertices and 7 edges with weights. Find the MST.

Edges in decreasing order of weight: (1-2, 8), (2-5, 7), (3-4, 6), (1-3, 5), (2-4, 4), (1-4, 3), (4-5, 2).

Greedy algorithm (Kruskal, starting from maximum weight — for the MST usually from minimal, but here for illustration):

Take the minimums: (4-5, 2): forest = {4-5} ✓. (1-4, 3): {4-5, 1-4} ✓. (2-4, 4): {4-5, 1-4, 2-4} ✓. (1-3, 5): {4-5, 1-4, 2-4, 1-3} ✓ — 4 edges for 5 vertices = tree.

MST = {4-5, 1-4, 2-4, 1-3}, weight = 2+3+4+5 = 14.