Schedule of Lectures

• 8/25:
  
  • Lecture: General announcements. Bipartite minimum-cost perfect matching.
  • Reading: Kozen, Lecture 19.
• 8/27:
  
  • Lecture: The LP relaxation of bipartite min-cost perfect matching and its dual. A primal-dual algorithm (the &\ldquo;Hungarian algorithm”) for bipartite min-cost perfect matching.
  • Reading: Lecture notes on a primal-dual algorithm for bipartite min-cost perfect matching. See also Section 7.13 of Kleinberg and Tardos.
• 8/30:
  
  • Lecture: Continuation of primal-dual min-cost matching algorithm.
  • Reading: Lecture notes on a primal-dual algorithm for bipartite min-cost perfect matching.
• 9/1:
  
  • Lecture: The Hopcroft-Karp algorithm for maximum unweighted bipartite matching.
  • Reading: Kozen, Lecture 20.
• 9/3:
  
  • Lecture: Class is canceled, but you may be interested to learn about Edmonds' non-bipartite matching algorithm.
  • Reading: Michel Goemans's lecture notes on non-bipartite matching.
• 9/6:
  
  • Lecture: No class because of Labor Day.
• 9/8:
  
  • Lecture: Network flow, the Ford-Fulkerson algorithm, and the Max-Flow Min-Cut Theorem.
  • Reading: Kozen, Lecture 16. Kleinberg-Tardos, Chapter 7.1 and 7.2.
• 9/10:
  
  • Lecture: Strongly polynomial max-flow algorithms: Edmonds-Karp and Dinitz.
  • Reading: Kozen, Lectures 17 and 18. A very interesting historical account of how these (and other) max-flow algorithms were discovered is contained in this paper by Yefim Dinitz. The paper also contains a technical exposition of Dinitz's algorithm, but the exposition in Kozen's book is easier to follow.
• 9/13:
  
  • Lecture: The preflow-push algorithm.
  • Reading: Kleinberg-Tardos, Chapter 7.4.
• 9/15:
  
  • Lecture: Combinatorial applications of max-flow.
  • Reading: Lecture notes on combinatorial applications of max-flow.
• 9/17:
  
  • Lecture: Introduction to matroids and minimum spanning trees.
  • Reading: Kozen, Lectures 2.1 and 3.
• 9/20-22:
  
  • Lecture: More on matroids and minimum spanning trees.
  • Reading: Lecture notes on Kruskal's and Boruvka's algorithms.
• 9/24-27:
  
  • Lecture: Karger, Klein, and Tarjan's linear-time randomized MST algorithm.
  • Reading: D. Karger, P. Klein, and R. Tarjan, A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42(2):321-328, 1995.
• 9/29-10/1:
  
  • Lecture: Matroid intersection.
  • Reading: Lecture 11 and Lecture 12 from Michel Goemans' combinatorial optimization class at MIT, Spring 2004.
• 10/4-6:
  
  • Lecture: Linear programming, the simplex method, and LP duality.
  • Reading: The lectures will primarily follow these notes by Vince Conitzer.
  • For an alternative treatment of the algorithm from a much more geometric perspective, see these notes by Avner Magen.
  • A helpful mnemonic for remembering how to form the dual of a linear program is the S-O-B method, described in this article by Arthur T. Benjamin.
• 10/8:
  
  • Lecture: The ellipsoid algorithm.
  • Reading: The lectures will follow these notes by Santosh Vempala.
• 10/13:
  
  • Lecture: Solving linear programs using multiplicative weights: the Plotkin-Shmoys-Tardos algorithm. NOTE: The preceding set of lectures actually ended on October 13, and consequently this topic was skipped.
  • Reading: Section 2 (at least up to Theorem 2.5) of Fast approximation algorithms for fractional packing and covering problems. S. Plotkin, D. Shmoys, and É. Tardos. Math. of Operations Research, 1995.
• 10/15:
  
  • MIDTERM EXAM: In-class test covering material up to and including the simplex method and LP duality. This will be an open-book, open-notes exam.
• 10/18:
  
  • Lecture: The Fast Fourier Transform, part I: Reduction from convolution to polynomial multiplication, and from polynomial multiplication to multi-point polynomial evaluation.
  • Reading: Kozen, Lecture 35. Kleinberg and Tardos, Section 5.6.
• 10/20:
  
  • Lecture: The Fast Fourier Transform, part II: Divide and conquer algorithm for evaluating polynomials at complex roots of unity.
  • Reading: Kozen, Lecture 35. Kleinberg and Tardos, Section 5.6.
• 10/22:
  
  • Lecture: FFT Applications: Fast pattern matching with “don't cares”.
  • Reading: Kalai, Efficient Pattern-Matching with Don't Cares, SODA 2003. Peter Clifford and Raphael Clifford, Simple Deterministic Wildcard Matching, Information Processing Letters 101 (2): 53-54, 2007.
• 10/25:
  
  • Lecture: Introduction to fast matrix multiplication: Strassen's algorithm. Fast LU decomposition, matrix inversion, determinant.
  • Reading: None. The following supplementary reading is not required, but may be useful for understanding parts of this lecture.
    • Bunch and Hopcroft, Triangular Factorization and Inversion by Fast Matrix Multiplication, Math. of Computation 28(125):231-236, Jan. 1974.
• 10/27:
  
  • Lecture: Application of fast matrix multiplication to perfect matchings in graphs. The Schwartz-Zippel Lemma.
  • Reading: Mucha and Sankowski, Maximum Matchings via Gaussian Elimination, FOCS 2004.
    The following additional materials are not required, but may be useful as supplementary material or to aid in understanding some parts of the lecture.
    • Chapter 3 of Marcin Mucha's Ph.D. thesis contains a more leisurely presentation of the preceding algorithm. is not required, but may be useful for understanding parts of this lecture.
    • Motwani and Raghavan, Randomized Algorithms, Chapters 7.2 and 7.3.
    • Harvey, Algebraic Algorithms for Matching and Matroid Problems, FOCS 2006, contains algorithms for non-bipartite matching and for matroid intersection inspired by the Mucha-Sankowski Gaussian Elimination technique.
• 10/29:
  
  • Lecture: Introduction to NP-Completeness. Basic definitions. Reductions from CNF-SAT to 3CNF-SAT and from 3CNF-SAT to Independent Set.
  • Reading: Kozen, Lectures 21 and 22.
• 11/1:
  
  • Lecture: Continuation of NP-Completeness. More on gadget reductions. NP-completeness of Hamiltonian Cycle.
  • Reading: Kozen, Lectures 23 and 24.
• 11/3:
  
  • Lecture: NP-completeness of Hamiltonian Path, Clique, Vertex Cover, Set Cover, Set Packing, Triple Matroid Intersection, Independent Set in Bounded-Degree Graphs.
  • Reading: None.
• 11/5:
  
  • Lecture: NP-complete numerical problems. Subset Sum, Partition, Load Balancing.
  • Reading: None.
• 11/8:
  
  • Lecture: Approximation Algorithms I: Polynomial-time approximation schemes. Approximation algorithms for the Knapsack problem.
  • Reading: Kleinberg-Tardos Chapters 11.1, 11.8.
• 11/10:
  
  • Lecture: Linear programming and approximation algorithm design. LP-rounding and primal-dual approximation algorithms for vertex cover.
  • Reading: Lecture notes on approximation algorithms, Sections 1.1 and 1.2.
• 11/12:
  
  • Lecture: The greedy set cover algorithm.
  • Reading: Lecture notes on approximation algorithms, Section 1.3.
• 11/15:
  
  • Lecture: Randomized approximation algorithms for max-cut and vertex cover.
  • Reading: Lecture notes on approximation algorithms, Section 2.
• 11/17:
  
  • Lecture: The Chernoff bound and a randomized approximation algorithm for congestion minimization in networks.
  • Reading: Lecture notes on approximation algorithms, Section 3.
• 11/19:
  
  • Lecture: Dynamic programming in graphs of bounded treewidth.
  • Reading: Kleinberg-Tardos, Chapter 10.4.
• 11/22,29:
  
  • Lecture: Markov chains and stationary distributions.
  • Reading: Alistair Sinclair's lecture notes on Markov chains and random walks, Lecture 2 and Lecture 3.
• 12/1:
  
  • CLASS CANCELED.
• 12/3:
  
  • Lecture: Bounding the mixing time of Markov chains using coupling.
  • Reading: Sinclair, Lecture 4 and Lecture 5.