MA515 Final Exam TopicsYou should be familiar with all of the definitions, examples, theorems, etc. But here are thespecific theorems that you should know the proofs for, and the specific algorithms that youshould be able to carry out.• Theorems and Pro ofs1. From my notes(a) Theorems 3.15 (Carath´eodory), 3.32 (H-Polytopes are V-Polytopes, Minkowski),and 3.36 (V-Polytopes are H-Polytopes, Weyl)(b) Theorems of the Alternatives, Theorems 7.2 and 7.3(c) Weak Duality, Theorem 9.1(d) Duality, Theorem 9.11(e) Complementary Slackness, Theorem 9.16, Corollaries 9.17, 9.182. From the book(a) Weyl’s Theorem for Polytopes, p. 11(b) Minkowski’s Theorem for Polytopes, p. 30(c) Unimodularity Implies Integrality, p. 41(d) Circuit Elimination, p. 52(e) Greedy Optimality for Matroids, p. 57(f) Validity of Dijkstra’s Algorithm, pp. 79–81 or my proof.(g) Matroid Intersection Duality Theorem, p. 99(h) Berge’s Theorem, p. 107(i) Matching Duality Theorem, p. 113(j) K¨onig’s Theorem, p. 44. You should be able to prove this three differentways: using total unimodularity, matroid intersection, or the max cardinalitymatching algorithm.• Algorithms1. From my notes(a) Fourier Motzkin Elimination(b) Be able to write the dual of a general linear program(c) Simplex Method(d) Revised Simplex Metho d2. From the book(a) Greedy Algorithm, Section 1.4(b) Be able to write down the inequalities for the Matroid Polytope, p. 67(c) Bellman-Ford, Floyd-Warshall, and Dijkstra’s Algorithm, Sections 2.1–2.3(d) Matroid Intersection Algorithm, Section 3.2(e) Be able to write down the inequalities for the Two Matroid Intersection Poly-tope, p. 103(f) Be able to write down the inequalities for the Matching Polytope, p. 109(g) Maximum Cardinality Matching Algorithm, Section
View Full Document
Unlocking...