LP-Based Algorithms
Course Outline
 		This course explores linear programming (LP) as a powerful and unifying framework for optimization and algorithm design. Topics we plan to cover include:
  • Introduction to linear programming, including problem modeling and algorithms for solving LPs
  • Duality theory and integrality of LP relaxations
  • Polyhedral descriptions of classical combinatorial objects, including matchings, T-joins, spanning trees, matroids, flows, and cuts
  • LP-based algorithmic techniques, such as randomized rounding, iterative rounding, and primal-dual methods, and its applications to approximation algorithms
  • Applications of linear programming in game theory
Prerequisites
 A good background in linear algebra as well as basic knowledge of algorithms and computational complexity will be required.
Details
 Classes will be held Tu/Thu 11:30-1pm in A-201.

Classes begin on January 27th.

Evaluation will be on the basis of assigments (50%), an in-class exam (25%), and a seminar (25%).

Reference material
 Good reference materials are

  • Introduction to Linear Optimization by Bertsimas and Tsitsiklis
  • Iterative Methods in Combinatorial Optimization by Lau, Singh, and Ravi
  • Approximation Algorithms by Vijay Vazirani
  • Theory of Linear and Integer Progamming by Schrijver
  • Understanding and Using Linear Programming by Matousek and Gartner
  • Combinatorial Optimization: Algorithms and Complexity by Papadimitriou and Steiglitz
  • The Design of Approximation Algorithms by Williamson and Shmoys
  • Geometric Algorithms and Combinatorial Optimization by Grotschel, Lovasz, and Schrijver.

For background in linear algebra, a good book is Introduction to Linear Alebra by Gilbert Strang.

I recommend taking notes in class, as our treatment will often differ from that in books, and I may cover topics out of order. I will post an outline of topics covered in each lecture below, including source material.

Lectures
Jan 27
 An example of LPs, and solving LPs graphically. General and standard forms of LPs. An example of such a conversion. Matrix notation. Defined vertices, extreme points, and basic feasible solutions, and proved equivalence of these three. My notes.

References: Sections 1.1, 1.4, 1.5, 2.1, and 2.2 from BT book.

Jan 29
 Importance of vertex solutions and the fundamental theorem of linear programming (without proof). A trivial algorithm for solving LPs on a polytope. A very brief description of the simplex algorithm on nondegenerate LPs in standard form: find a starting bfs; find an adjacent bfs of lower cost and move there; repeat until all adjacent bfs have equal or higher cost. My notes.

References: Section 2.3, 2.4, 2.5 2.6, and the first few parts of Section 3.1 from BT book.

Feb 3
 The ellipsoid algorithm, skipping a lot of technical details. My notes.

References: Section 8.3 from BT.

Feb 5
 LP duality. Proof of strong duality using the simplex algorithm. Complementary slackness. My notes.

References: Sections 4.1, 4.2 and 4.3 from BT

Feb 12
 Farkas Lemma. Proof of strong duality using FL. Proof of FL. Application of FL to max flows and min cuts. My notes.

References: Sections 4.6 and 4.7.

Feb 17
 Total unimodularity and total dual integrality, with applications to max flows and maximum matchings. My notes.

References: References: The main reference is Chapter 19 from the Schrijver book, but the material selection is quite selective. For total dual integrality, I referred to notes by Chandra Chekuri.

Feb 19
 Augmenting path algorithm for maximum cardinality bipartite matching, Hungarian algorithm for minimum weight perfect matchings.

References: Notes by Michel Goemans.

Feb 24
 Matching polytope for general graphs.

References: Notes by Jan Vondrak.

Feb 26
 Minimum odd-cuts, T-joins

References: Notes by Michel Goemans (Section 4.5)

Mar 5
 Maximum cardinatily matching in general graphs: Blossom algorithm; Tutte's Theorem

References: Notes by Michel Goemans

Mar 10
 Matroids: defintion, examples, greedy algorithm for finding a maximum weight Independent-Set.

References: Notes by Michel Goemans

Mar 12
 Rank function of a matroid, matroid polytope (algorithmic and vertex proof)

References: Notes by Michel Goemans

Mar 17
 Matroid Intersection: definition, examples and polyhedral description, primal-dual algorithm for the minimum cost arborescence problem.

References: Notes by Michel Goemans

Mar 24
 Equivalence of polyhedra, by focusing on facets. Class taken by Kavitha.

References: Notes by Michel Goemans

Mar 26
 Smallest Compact Formulation for the permutahedron. Class taken by Kavitha.

References: This paper by Michel Goemans

Assignment Policies
  • You may discuss the problems with others in the class, but you must write up the solution by yourself, in your own words.
  • Please write in your submission the people with whom you discussed the problems, as well as any references you used.
  • Please write clearly and succinctly, and include how you arrived at the solution!
Assignments