next up previous
Next: About this document

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 tex2html_wrap_inline34 be a finite subset of tex2html_wrap_inline36 . Let P=conv tex2html_wrap_inline40 be the convex hull of V. Let tex2html_wrap_inline44 be a subset of tex2html_wrap_inline36 . Assume that tex2html_wrap_inline48 . 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 tex2html_wrap_inline56 . 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 tex2html_wrap_inline62 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.
  1. Problem (Minors of matroids) p.15

Carl Lee
Fri Feb 5 13:40:45 EST 1999