LP-based Algorithms
Course outline
 In this course, we will learn how linear programming (LP) serves as a powerful and unifying tool in optimization and algorithms. Topics we plan to cover include:
  • an introduction to linear programming (including modeling problems and solving LPs)
  • duality and integrality
  • LP-based techniques for classical problems in combinatorial optimization, including matchings, spanning trees, arborescences, matroids, flows and cuts
  • submodular optimization
  • degree-bounded spanning trees, packing arborescences, generalised assignment, SNDP, k-ECSS
  • LP-based techniques for approximation algorithms, including randomized rounding, iterative rounding, and primal-dual algorithms
  • applications of LPs 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.

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