Matroids & Exchange Arguments

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.

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.

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.¹ 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.

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.

A first consequence of the exchange property is that all bases have the same size.

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 $I$ the linearly independent subsets, form the linear matroid; this is where the vocabulary comes from.)

The exchange property — any smaller independent set

A

can absorb some

x \in B ∖ A

from a larger one

Because $∣ A ∣ < ∣ B ∣$ , some $x \in B ∖ A$ (here $c$ ) joins $A$ keeping it independent, so no maximal independent set is left stranded below the rank.

matroid.pypython

from abc import ABC, abstractmethod
from collections.abc import Callable, Hashable, Iterable
from typing import Generic, Optional, TypeVar


Element = TypeVar("Element", bound=Hashable)


class Matroid(ABC, Generic[Element]):
  """
    The matroid contract over a finite ground set of hashable elements.\n
    Concrete matroids supply `ground_set` and an `is_independent` test;\n
    the abstract base derives rank, bases, and the exchange witness from\n
    those two, so every matroid plugs straight into `matroid_greedy`.\n
  """

  @abstractmethod
  def ground_set(self) -> list[Element]:
    """
      Every element of the ground set S.\n
    """
    raise NotImplementedError

  @abstractmethod
  def is_independent(self, subset: frozenset[Element]) -> bool:
    """
      Whether `subset` belongs to the family of independent sets I.\n
    """
    raise NotImplementedError

  def can_extend(
    self,
    independent: frozenset[Element],
    element: Element,
  ) -> bool:
    """
      Whether adding `element` keeps an already-independent set independent.\n
    """
    return self.is_independent(independent | {element})

  def exchange_witness(
    self,
    smaller: frozenset[Element],
    larger: frozenset[Element],
  ) -> Optional[Element]:
    """
      An element of `larger \\ smaller` that extends `smaller` and keeps it\n
      independent, or None. On a genuine matroid with |smaller| < |larger|\n
      and both independent, the exchange property guarantees this is not\n
      None — useful for empirically checking the axiom.\n
    """
    # first element of the difference that keeps `smaller` independent.
    for element in larger - smaller:
      if self.can_extend(smaller, element):
        return element
    return None

  def is_base(self, subset: frozenset[Element]) -> bool:
    """
      Whether `subset` is a base: independent and not extendable by any\n
      element of the ground set.\n
    """
    if not self.is_independent(subset):
      return False

    # a base admits no further element of the ground set.
    for element in self.ground_set():
      if element not in subset and self.can_extend(subset, element):
        return False
    return True

  def rank(self) -> int:
    """
      The rank r(M): the common size of every base, found by greedily\n
      growing the empty set with unit weights.\n
    """
    return len(self.find_base())

  def find_base(self) -> set[Element]:
    """
      Some base of the matroid, built by greedy extension from the empty\n
      set. All bases share the rank, so any one suffices for sizing.\n
    """
    base: set[Element] = set()
    current: frozenset[Element] = frozenset()

    # grow greedily, absorbing every element the running set can take.
    for element in self.ground_set():
      if self.can_extend(current, element):
        base.add(element)
        current = current | {element}
    return base


def is_matroid(structure: Matroid[Element]) -> bool:
  """
    Brute-force check that `structure` actually satisfies the matroid\n
    axioms over its ground set: nonempty I, hereditary closure, and the\n
    exchange property on every pair of independent sets. Exponential in the\n
    ground-set size, so for small instances only — handy for confirming a\n
    structure is (or is not) a matroid, as the lesson does for knapsack.\n
  """
  elements: list[Element] = structure.ground_set()
  independents: list[frozenset[Element]] = _all_independent_sets(structure)

  # nonempty family: the empty set must be independent.
  if frozenset() not in independents:
    return False

  # hereditary: every subset of an independent set is independent.
  independent_lookup: set[frozenset[Element]] = set(independents)
  for subset in independents:
    for element in subset:
      if (subset - {element}) not in independent_lookup:
        return False

  # exchange: any smaller independent set absorbs an element of a larger one.
  for smaller in independents:
    for larger in independents:
      if len(smaller) < len(larger):
        if structure.exchange_witness(smaller, larger) is None:
          return False

  _ = elements
  return True


def _all_independent_sets(
  structure: Matroid[Element],
) -> list[frozenset[Element]]:
  """
    Every independent subset of the ground set, by exhaustive enumeration.\n
  """
  elements: list[Element] = structure.ground_set()
  independents: list[frozenset[Element]] = []

  # each bitmask picks one subset; keep the ones that test independent.
  for mask in range(1 << len(elements)):
    chosen: frozenset[Element] = frozenset(
      elements[index]
      for index in range(len(elements))
      if mask & (1 << index)
    )
    if structure.is_independent(chosen):
      independents.append(chosen)
  return independents

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 $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:

\textsc{Greedy}(M=(S,\mathcal I),\, w)

— maximum-weight independent set

1
$A \gets \varnothing$
2
sort $S$ into nonincreasing order by weight $w$
3
for each $x \in S$ in sorted order do
4
if $A \cup \{x\} \in \mathcal{I}$ then
independence test
5
$A \gets A \cup \{x\}$
6
return $A$

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}) \geq w (g_{2}) \geq \dots \geq 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}) \geq w (o_{i})$ for all $i$ and $w (G) \geq 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 ∖ A$ with $A \cup {o_{j}} \in I$ . Each $o_{i} \in B$ has $w (o_{i}) \geq 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. $□$

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.

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}) < w (o_{k})

(red). The exchange property on

A = {g_{1} \dots g_{k - 1}}

and

B = {o_{1} \dots o_{k}}

yields a heavier independent extension greedy would have taken first.

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$ .

matroid.pypython

from abc import ABC, abstractmethod
from collections.abc import Callable, Hashable, Iterable
from typing import Generic, Optional, TypeVar


Element = TypeVar("Element", bound=Hashable)


class Matroid(ABC, Generic[Element]):
  """
    The matroid contract over a finite ground set of hashable elements.\n
    Concrete matroids supply `ground_set` and an `is_independent` test;\n
    the abstract base derives rank, bases, and the exchange witness from\n
    those two, so every matroid plugs straight into `matroid_greedy`.\n
  """

  @abstractmethod
  def ground_set(self) -> list[Element]:
    """
      Every element of the ground set S.\n
    """
    raise NotImplementedError

  @abstractmethod
  def is_independent(self, subset: frozenset[Element]) -> bool:
    """
      Whether `subset` belongs to the family of independent sets I.\n
    """
    raise NotImplementedError

  def can_extend(
    self,
    independent: frozenset[Element],
    element: Element,
  ) -> bool:
    """
      Whether adding `element` keeps an already-independent set independent.\n
    """
    return self.is_independent(independent | {element})

  def exchange_witness(
    self,
    smaller: frozenset[Element],
    larger: frozenset[Element],
  ) -> Optional[Element]:
    """
      An element of `larger \\ smaller` that extends `smaller` and keeps it\n
      independent, or None. On a genuine matroid with |smaller| < |larger|\n
      and both independent, the exchange property guarantees this is not\n
      None — useful for empirically checking the axiom.\n
    """
    # first element of the difference that keeps `smaller` independent.
    for element in larger - smaller:
      if self.can_extend(smaller, element):
        return element
    return None

  def is_base(self, subset: frozenset[Element]) -> bool:
    """
      Whether `subset` is a base: independent and not extendable by any\n
      element of the ground set.\n
    """
    if not self.is_independent(subset):
      return False

    # a base admits no further element of the ground set.
    for element in self.ground_set():
      if element not in subset and self.can_extend(subset, element):
        return False
    return True

  def rank(self) -> int:
    """
      The rank r(M): the common size of every base, found by greedily\n
      growing the empty set with unit weights.\n
    """
    return len(self.find_base())

  def find_base(self) -> set[Element]:
    """
      Some base of the matroid, built by greedy extension from the empty\n
      set. All bases share the rank, so any one suffices for sizing.\n
    """
    base: set[Element] = set()
    current: frozenset[Element] = frozenset()

    # grow greedily, absorbing every element the running set can take.
    for element in self.ground_set():
      if self.can_extend(current, element):
        base.add(element)
        current = current | {element}
    return base


def matroid_greedy(
  matroid: Matroid[Element],
  weight: Callable[[Element], float],
) -> list[Element]:
  """
    Rado-Edmonds greedy: return a maximum-weight base of `matroid`.\n
    Sort the ground set by weight descending and accept each element whose\n
    addition keeps the running set independent. The returned list is in the\n
    order the elements were accepted (nonincreasing weight). This is the\n
    lesson's pseudocode verbatim; on a matroid with positive weights the\n
    result is a maximum-weight base. The min-spanning-tree reduction runs\n
    this on negated weights, which is why no element is filtered by sign.\n
  """
  # consider elements heaviest-first.
  ordered: list[Element] = sorted(
    matroid.ground_set(),
    key=weight,
    reverse=True,
  )

  # accept each element the running independent set can still take.
  chosen: list[Element] = []
  current: frozenset[Element] = frozenset()
  for element in ordered:
    if matroid.can_extend(current, element):
      chosen.append(element)
      current = current | {element}
  return chosen

Examples that are matroids

The graphic matroid. Let $G = (V, E)$ be a graph. Take $S = E$ and let $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 $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 cycle check from the minimum spanning trees lesson. So Kruskal's correctness is the Rado–Edmonds theorem instantiated on the graphic matroid.

Acyclic edge sets form a matroid — Kruskal is matroid-greedy, taking edges by weight and rejecting any that close a cycle

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 $I$ . The accepted set is a base: a spanning tree.

graphic_matroid.pypython

from collections.abc import Hashable
from typing import Generic, NamedTuple, TypeVar

from matroid import Matroid
from union_find import UnionFind

Label = TypeVar("Label", bound=Hashable)

class WeightedEdge(NamedTuple, Generic[Label]):
  """
    An undirected weighted edge between two vertex labels.\n
    Hashable, so it can serve directly as a matroid ground-set element.\n
  """
  first: Label
  second: Label
  weight: float

class GraphicMatroid(Matroid[WeightedEdge[Label]]):
  """
    The cycle matroid of an undirected graph: edges as the ground set,\n
    acyclic edge sets (forests) as the independent sets.\n
    Independence is tested by union-find — a set is a forest exactly when\n
    no edge joins two endpoints already in the same component.\n
  """

  def __init__(self, edges: list[WeightedEdge[Label]]) -> None:
    self._edges: list[WeightedEdge[Label]] = list(edges)

  def ground_set(self) -> list[WeightedEdge[Label]]:
    return list(self._edges)

  def is_independent(
    self,
    subset: frozenset[WeightedEdge[Label]],
  ) -> bool:
    """
      Whether the chosen edges form a forest (no cycle), via union-find.\n
    """
    # seed a singleton component for every endpoint.
    components: UnionFind[Label] = UnionFind()
    for edge in subset:
      components.add(edge.first)
      components.add(edge.second)

    # an edge whose endpoints already share a component closes a cycle.
    for edge in subset:
      if not components.union(edge.first, edge.second):
        return False
    return True

def kruskal_mst(
  edges: list[WeightedEdge[Label]],
) -> list[WeightedEdge[Label]]:
  """
    Kruskal's minimum spanning forest as matroid-greedy on negated weights.\n
    Sort edges by weight ascending and keep each that does not close a\n
    cycle. Returns the chosen edges in the order accepted; for a connected\n
    graph this is a minimum spanning tree.\n
  """
  # lightest edges first.
  ordered: list[WeightedEdge[Label]] = sorted(
    edges,
    key=lambda edge: edge.weight,
  )

  # every vertex starts in its own component.
  components: UnionFind[Label] = UnionFind()
  for edge in edges:
    components.add(edge.first)
    components.add(edge.second)

  # keep an edge only when it merges two distinct components (no cycle).
  forest: list[WeightedEdge[Label]] = []
  for edge in ordered:
    if components.union(edge.first, edge.second):
      forest.append(edge)
  return forest

union_find.pypython

from collections.abc import Hashable, Iterable
from typing import Generic, TypeVar, cast


Element = TypeVar("Element", bound=Hashable)


class DisjointSetNode(Generic[Element]):
  """
    One element's node: its value, its parent link, and its rank.\n
    A node is its own parent exactly when it is the root of its set.\n
  """

  def __init__(self, value: Element) -> None:
    self.value: Element = value
    self.parent: DisjointSetNode[Element] = self
    self.rank: int = 0

  def __repr__(self) -> str:
    return f"DisjointSetNode({self.value!r})"


class UnionFind(Generic[Element]):
  """
    A collection of disjoint sets over hashable elements.\n
  """

  def __init__(self, elements: int | Iterable[Element] = 0) -> None:
    """
      Seed the structure. An int `n` creates singletons `0..n-1`;\n
      an iterable creates one singleton node per member.\n
    """
    # a seed count `n` means the elements are 0..n-1 (ints standing in for
    # Element); cast keeps the type checker happy about that substitution.
    members: Iterable[Element] = (
      cast("Iterable[Element]", range(elements))
      if isinstance(elements, int)
      else elements
    )
    # one singleton node per seeded member.
    self._nodes: dict[Element, DisjointSetNode[Element]] = {
      value: DisjointSetNode(value) for value in members
    }
    self.count: int = len(self._nodes)

  def add(self, value: Element) -> None:
    """
      Add `value` as a new singleton set if it is absent.\n
    """
    if value not in self._nodes:
      self._nodes[value] = DisjointSetNode(value)
      self.count += 1

  def _find_root(self, value: Element) -> DisjointSetNode[Element]:
    """
      The root node of `value`'s set, compressing the path on the way.\n
    """
    # first pass: climb parent links to the root of the set.
    node = self._nodes[value]
    root = node
    while root.parent is not root:
      root = root.parent

    # second pass: point every node on the path straight at the root.
    while node.parent is not root:
      node.parent, node = root, node.parent

    return root

  def find(self, value: Element) -> Element:
    """
      The representative value of `value`'s set.\n
    """
    return self._find_root(value).value

  def union(self, first: Element, second: Element) -> bool:
    """
      Merge the sets containing `first` and `second`.\n
      Returns False if they already shared a set.\n
    """
    # already in the same set: nothing to merge.
    first_root = self._find_root(first)
    second_root = self._find_root(second)
    if first_root is second_root:
      return False

    # hang the shorter tree under the taller one.
    if first_root.rank < second_root.rank:
      first_root, second_root = second_root, first_root
    second_root.parent = first_root

    # equal ranks: the merged tree grows one level taller.
    if first_root.rank == second_root.rank:
      first_root.rank += 1

    self.count -= 1
    return True

  def connected(self, first: Element, second: Element) -> bool:
    """
      Whether `first` and `second` belong to the same set.\n
    """
    return self._find_root(first) is self._find_root(second)

The uniform / partition matroid. Even simpler: fix $k$ and let $I = {A \subseteq S : ∣ A ∣ \leq 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.

The uniform matroid

U_{3, 6}

: independent means

∣ A ∣ \leq 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.

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.

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).

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.

uniform_matroid.pypython

from collections.abc import Callable, Hashable, Iterable, Mapping
from typing import Generic, TypeVar

from matroid import Matroid

Element = TypeVar("Element", bound=Hashable)
Group = TypeVar("Group", bound=Hashable)

class UniformMatroid(Matroid[Element]):
  """
    U(k, n): subsets of size at most `capacity` over `elements`.\n
    The exchange property is immediate — a larger independent set always has\n
    a spare element — so greedy here is just "pick the k heaviest."\n
  """

  def __init__(self, elements: Iterable[Element], capacity: int) -> None:
    self._elements: list[Element] = list(elements)
    if capacity < 0:
      raise ValueError("capacity must be non-negative")
    self.capacity: int = capacity

  def ground_set(self) -> list[Element]:
    return list(self._elements)

  def is_independent(self, subset: frozenset[Element]) -> bool:
    return len(subset) <= self.capacity

class PartitionMatroid(Matroid[Element], Generic[Element, Group]):
  """
    A partition matroid: each element belongs to a group, and a subset is\n
    independent when it holds at most `cap(group)` elements of every group.\n
    Models "no more than c of this kind" assignment constraints.\n
  """

  def __init__(
    self,
    group_of: Mapping[Element, Group],
    caps: Mapping[Group, int],
  ) -> None:
    self._group_of: dict[Element, Group] = dict(group_of)
    self._caps: dict[Group, int] = dict(caps)

    # every group an element belongs to needs a declared cap.
    for group in set(self._group_of.values()):
      if group not in self._caps:
        raise ValueError(f"no cap supplied for group {group!r}")

  def ground_set(self) -> list[Element]:
    return list(self._group_of)

  def is_independent(self, subset: frozenset[Element]) -> bool:
    # tally per group and reject as soon as any cap is exceeded.
    counts: dict[Group, int] = {}
    for element in subset:
      group: Group = self._group_of[element]
      counts[group] = counts.get(group, 0) + 1
      if counts[group] > self._caps[group]:
        return False
    return True

def heaviest_k(
  elements: Iterable[Element],
  capacity: int,
  weight: Callable[[Element], float],
) -> list[Element]:
  """
    The closed form of greedy on U(k, n): the `capacity` heaviest elements\n
    (ignoring non-positive weights). Equivalent to `matroid_greedy` on a\n
    `UniformMatroid`, kept as a direct reference for the tests.\n
  """
  # drop non-positive weights, then take the heaviest `capacity` of the rest.
  positives: list[Element] = [
    element for element in elements if weight(element) > 0
  ]
  ordered: list[Element] = sorted(positives, key=weight, reverse=True)
  return ordered[:capacity]

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 lesson that greedy fails on the 0/1 knapsack, and from the knapsack DP 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.

0/1 knapsack is not a matroid (

W = 8

). The independent set

{7}

and the larger

{4, 4}

both fit, yet adding either

4

{7}

gives

11 > 8

. No element of the larger set can grow the smaller, so the exchange property fails.

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 $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.³ 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.⁴ 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 $P = NP$ .⁵ 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.

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.

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, 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, 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, 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, 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. ↩
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. ↩
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. ↩