Next: About this document
MA618 Homework #3
Due Friday, February 12
Problems to turn in
Problems to do but not 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
Later, try to handle the case when some elements of the matroid have the
- Read Appendix A2.
- Let be a finite subset of .
Let P=conv be the convex hull of V.
Let be a subset of . Assume
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