Advanced Heuristic and Approximation Algorithms (Grenoble INP, M2 2018-2019)



Course Topics

Lecture Schedule

 Introduction to Convex Relaxations Friday October 5 Lecture 1
 LP Duality Monday October 8 Lecture 2
 Duality-Based LP Rounding Friday October 12 Lecture 3
 Randomized LP Rounding Monday October 22 Lecture 4
 Heuristics for Solving Convex Programs Monday November 5 See: Section 2    Section 17.2.4    Extra                       Homework 1    Solutions
 Hoffman Circulation Theorem Monday November 12 Lecture 6
 Algorithms for Asymmetric TSP Monday November 19 See: This paper
 Spectral Partitioning Friday November 23 Lecture 8        Based on Chapters 1 and 2 from these notes by Luca Trevisan
 Unique Games Monday November 26 See: This paper
 Unique Games Continued Monday December 3
 Hashing and Dimension Reduction Friday December 14 See: Section 1    Section 3    Sections 3 and 4                      
 Streaming and Counting Distinct Elements Monday December 17 See: These notes                       Homework 2     (Partial) Solutions
 Final Exam Friday January 24

Useful Resources

  1. The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys
  2. Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan at UC Berkeley
  3. Iterative Methods in Combinatorial Optimization by Lap Chi Lau, R. Ravi and Mohit Singh
  4. Cornell University Course on Mathematical Programming by David P. Williamson
  5. Stanford University Course on Algorithmic Techniques for Big Data by Moses Charikar