MS&E 217/317, Combinatorial Optimization, Autumn 2003-04.Instructor: Ashish Goel

Handout 4

HW 2 addendum on Matroids (for MS&E 317 students only).

Given 10/24/2003, Due 10/31/2003, in class, or in my office (by 11am).

No collaboration allowed.

1. Problem 8.5 from the text.

2. You are given a matroid (S,I) with weight function w. Show how to find another weight function x, so that the if the greedy Matroid algorithm is run on (S,I,x) it produces a maximal independent set of minimum weight for the original problem (S,I,w). Prove that Kruskal’s algorithm is equivalent to doing this transformation on the Graphic Matroid and then running the greedy Matroid algorithm. Observe that this is an alternate proof of the correctness of Kruskal’s algorithm.

MS&E 317: If you do this HW, you only need to solve one out of problems 3 and 4 in HW 2, and can also take one additional problem off from the next HW (I will specify which – you won’t get to choose!).