Greedy Algorithm may not yield Maximum Weight

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S,\mathscr F}$ be an independence system.

Let $w : S \to \R_{\ge 0}$ be a weight function.


Then the maximal set $A_0 \in \mathscr F$ selected by the Greedy Algorithm may not have maximum weight.


Proof