Greedy Algorithm guarantees Maximum Weight iff Matroid

Theorem

Let $S$ be a finite set.

Let $\mathscr I$ be a non-empty set of subsets of $S$.

Then $\mathscr I$ is the set of independent subsets of a matroid on $S$ if and only if:

$(1) \quad \struct{S, \mathscr I}$ is an independence system

$(2) \quad$ for all non-negative weight functions $w : S \to \R_{\ge 0}$, the Greedy Algorithm selects $A_w \in \mathscr I$:

$\forall B \in \mathscr I: \map {w^+} {A_w} \ge \map {w^+} B$

where $w^+$ denotes the extended weight function of $w$.

Proof

This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Sources

• 1976: Dominic Welsh: Matroid Theory Chapter $19.$ $\S 1.$ The greedy algorithm