**MA618 Homework #3
Due Friday, February 12
**

**
Problems to turn in
**

**Problem (Swapping algorithm) p.12. Suggestion: First assume that the weights are all different. Let***S*be the given independent set and let*T*be the maximum weight independent set of size*k*found by the Greedy Algorithm. Consider the lowest index on which*S*and*T*differ.Later, try to handle the case when some elements of the matroid have the same weight.

**Read Appendix A2.****Let be a finite subset of . Let***P*=conv be the convex hull of*V*. Let be a subset of . Assume that . Prove that the following linear program has an optimal solution in*V*for every objective function*c*if and only if*Q*=*P*:For one direction, assume that there is a point . Express the statement that

*q*can be written as a convex combination of the points in*V*in the form of a system of equations and inequalities (which is therefore infeasible). Maximize the objective function over this system and look at the dual. Alternatively, use a theorem of the alternatives.

- Exercise (Dual solution) p.18.

- Problem (Minors of matroids) p.15

Fri Feb 5 13:40:45 EST 1999