Greedy Algorithm may not yield Maximum Weight
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
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. |