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



Course Topics

(Tentative) 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 Room F111
 Randomized LP Rounding Monday October 22
 Heuristics for Solving Convex Programs Monday November 5
 Hoffman Circulation Theorem Monday November 12
 Algorithms for Asymmetric TSP Monday November 19
 Spectral Partitioning Friday November 23
 Unique Games Monday November 26
 Small-Set Expansion Monday December 3
 Algorithms for Data Analysis I Friday December 7
 Algorithms for Data Analysis II Monday December 17
 Final Exam January ??

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