[SV] Notes by Prof. Sundar Vishwanathan

- Jan 3: Introduction to linear programming, examples (Chapter 1 of [MG])
- Jan 5: Expressing computational problems as linear programs (Chapter 2 of [MG])
- Jan 18: Linear programs in equational form, Basic feasible solutions, convexity and convex polyhedra (Chapter 4 of [MG])
- Jan 20: Recap of basic concepts from linear algebra: vector spaces, linear combinations, basis, dimension, row space, column space, and null space of a matrix, row rank=column rank (Appendix of [MG])
- Jan 20: Vertex of the feasible region of an LP, basic feasible solutions and optimality, execution of the simplex method (Chapter 4 and Section 5.1 of [MG])
- Jan 25: Simplex continued: unboundedness, degeneracy, finding initial BFS using artificial variables (Sections 5.2,5.3,5.4 of [MG])
- Jan 27: Formal description of simplex method, pivot rules, efficiency and Klee-Minty example (Sections 5.5,5.6,5.6,5.9 of [MG])

Several references e.g. this one give examples for cycling - Feb 1: Simplex doesn't cycle: Proof of Bland's rule (Section 5.8 of [MG])
- Feb 8: LP duality: Construction of dual and weak duality (Section 6.1,6.2 from [MG])
- Feb 15: Proof of LP duality from simplex method, statement of Farka's lemma (Section 6.3 of [MG])
- Feb 17: Relation between strong duality and Farka's lemma (Section 6.4 of [MG])
- Mar 1: Complementary slackness, primal-dual method, a primal-dual algorithm for directed shortest paths Ref
- Mar 3: Primal-dual algorithm (Kruskal's) for minimum spanning trees Ref
- Mar 10: Introduction to network flows, Max-flow min-cut theorem via LP duality, introduction to matchings (Ref: Algorithms by Dasgupta, Papadimitrou, Vazirani)
- Mar 15: Bipartite matching and vertex cover as primal-dual pairs, Algorithmic proof of König's theorem (Ref)
- Mar 17: Integrality of bipartite perfect matching polytope (Ref: same as above)
- Mar 22: 1/2-integrality of vertex cover polytope and 2-approximation by rounding, weighted vertex cover 2-approximation by primal-dual (Ref and this)
- Mar 24: Integrality of non-bipartite perfect matching polytope (ref)
- Mar 29: Total unimodularity (Ref: relevant parts of Chapter 19 of Schrijver's book titled Theorey of Linear and Integer Programming)
- Mar 31: Strongly vs weakly polynomial-time, introduction to ellipsoid algorithm (Ref: Section 7.1 of [MG], these notes)
- Apr 5: Details of ellipsoid algorithm (Ref: same as above)
- Apr 12: Application of ellipsoid algorithm for solving LP with exponentially many constraints and polynomial-time separation oracle: Non-bipartite matching (Reference, also see Section 6.5 of this)
- Apr 19: A brief overview of interior point methods (Section 7.2 of Matousek's book), Complexity of ILP (Reference)

Feb 3: Class cancelled due to Tessellate

Mar 8: Class cancelled due to Prof. Howard Straubing's lecture