MA618 Homework #3
Due Friday, February 12

Problems to turn in

1. 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.

2. Read Appendix A2.
3. 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.

Problems to do but not to turn in

1. Exercise (Dual solution) p.18.

Postponed

1. Problem (Minors of matroids) p.15

• About this document ...