Schedule of Lectures

• 8/28:
  
  • Lecture: Course overview.
    Matchings I: Bipartite maximum matching. Augmenting paths.
  • Reading: Kozen, Lecture 19.
• 8/30:
  
  • Lecture: Matchings II: The Hopcroft-Karp algorithm.
  • Reading: Kozen, Lecture 20.
• 9/2:
  
  • No class because of Labor Day
• 9/4:
  
  • Lecture: Matchings III: Bipartite min-cost perfect matching, its LP relaxation, and its dual.
  • Reading: Lecture notes on a primal-dual algorithm for bipartite min-cost perfect matching.
• 9/6:
  
  • Lecture: Matchings IV: Primal-dual 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.
• 9/9:
  
  • Lecture: Matchings V: Completing primal-dual 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.
• 9/11:
  
  • Lecture: Matchings VI: Online bipartite matching.
  • Reading: Lecture notes on online bipartite matching algorithms.
    (Section 3 is loosely based on Buchbinder, Jain, and Naor, Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue, ESA 2007.)
• 9/13:
  
  • Lecture: Matching VII: Finish online bipartite matching.
  • Reading: Lecture notes on online bipartite matching algorithms.
    (Section 3 is loosely based on Buchbinder, Jain, and Naor, Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue, ESA 2007.)
• 9/16:
  
  • Lecture: Network Flow I: Network flow and the Max-Flow Min-Cut Theorem.
  • Reading: Kozen, Lecture 16. (Alternate: Kleinberg-Tardos, Chapter 7.1 and 7.2.)
• 9/18:
  
  • Lecture: Network Flow II: Ford-Fulkerson and Edmonds-Karp.
  • Reading: Kozen, Lecture 17.
• 9/20:
  
  • Lecture: Network Flow III: Combinatorial applications of max-flow.
  • Reading: Lecture notes on combinatorial applications of max-flow.
• 9/23:
  
  • Lecture: Network Flow IV: Dinitz's algorithm.
  • Reading: Kozen, Lecture 18.
    A very interesting historical account of how this 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/25:
  
  • Lecture: Network Flow V: Preflow-Push.
  • Reading: Kleinberg-Tardos, Chapter 7.4.
• 9/27:
  
  • Lecture: Linear programming I: Introduction to linear programming.
  • Reading: None.
• 9/30:
  
  • Lecture: Linear programming II: The simplex method.
  • Reading: The lectures will primarily follow these notes by Vince Conitzer.
• 10/4:
  
  • Lecture: Linear programming III: LP duality.
  • Reading: None.
• 10/7:
  
  • Lecture: Linear programming IV: The ellipsoid method.
  • Reading: The lectures will follow these notes by Santosh Vempala.
• 10/9:
  
  • Lecture: Multiplicative weights algorithms I: Prediction from expert advice.
  • Reading: Lecture notes on the multiplicative weights update method, Section 1.
• 10/11:
  
  • Lecture: Multiplicative weights algorithms II: Approximately solving packing and covering LPs.
  • Reading: Lecture notes on the multiplicative weights update method, Section 2.
• 10/16:
  
  • Lecture: Multiplicative weights algorithms III: Multicommodity flow (uniform capacity case).
  • Reading: Lecture notes on the multiplicative weights update method, Section 3.
• 10/18:
  
  • Lecture: Multiplicative weights algorithms IV: Multicommodity flow (general case).
  • Reading: Lecture notes on the multiplicative weights update method, Section 3.
• 10/21:
  
  • Lecture: The sparsest cut problem and its LP relaxation. Dependent rounding algorithm for approximate sparsest cut.
  • Reading: Lecture notes on the multiplicative weights update method, Section 4.
• 10/23:
  
  • Lecture: Spectral Methods I: The graph Laplacian.
  • Reading: Lecture notes on spectral methods in algorithm design, Sections 1-3.
• 10/25:
  
  • Lecture: Spectral Methods II: Spectral algorithm for approximate sparsest cut; Cheeger's inequality.
  • Reading: Lecture notes on spectral methods in algorithm design, Sections 4-6.
• 10/28:
  
  • LECTURE CANCELED.
• 10/30:
  
  • Lecture: Spectral Methods III: The planted clique problem.
  • Guest lecturer: David Steurer
  • Reading: N. Alon, M. Krivelevich, and B. Sudakov, Finding a large hidden clique in a random graph, Rand. Struct. Algorithms 13 (1998), 457-466.
    The lecture will cover Sections 1 and 2 of the paper only.
• 11/1:
  
  • Lecture: Spectral Methods IV: Clustering mixtures of Gaussians.
  • Guest lecturer: John Hopcroft
  • Reading: None.
• 11/4:
  
  • Lecture: Complexity I: The complexity classes P and NP, polynomial time many-one reductions, reducing 3SAT to Independent Set.
  • Reading: Kozen, Lecture 22.
• 11/6:
  
  • Lecture: Complexity II: NP-Completeness of Exact Cover, Subset Sum, Partition, Knapsack.
  • Reading: Kozen, Lectures 23.3 and 24.
• 11/8:
  
  • Lecture: Complexity III: NP-Completeness of Hamiltonian Circuit.
  • Reading: Kozen, Lecture 24.
• 11/11:
  
  • Lecture: Approximation Algorithms I: LP rounding and primal-dual.
  • Reading: Sections 1, 2 of approximation algorithms handout.
• 11/13:
  
  • Lecture: Approximation Algorithms II: Greedy set cover.
  • Reading: Section 2.3 of approximation algorithms handout.
• 11/15:
  
  • Lecture: Approximation Algorithms III: Randomized approximation algorithms.
  • Reading: Section 3 of approximation algorithms handout.
• 11/18:
  
  • Lecture: Approximation Algorithms IV: Linear programming with randomized rounding.
  • Reading: Section 4 of approximation algorithms handout.
• 11/20:
  
  • Lecture: Approximation Algorithms V: Polynomial time approximation schemes.
  • Reading: Section 11.8 of Kleinberg & Tardos.