Greedy Algorithm Proofs
1) Let M be a matroid and w: E(M)->R. When the greedy algorithm is applied to the pair (I(M),w) each application of the step involves a potential choice. Thus in general, there are a number o different sets that the algorithm can produce as solutions to the optimization problem (I(M),w). Let Bg be the set o such sets and Bmax be the set of maximum-weight bases of M. Prove Bg=Bmax
2) Let M be a matroid and w: E(M) -> R be a one-to-one. function. Prove that M has a unique basis of maximum weight.
Thanks for any help !