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




(Tentative) Course Topics

Lecture Schedule

 Introduction Monday October 2                            Exercises
 Minimum Cut Monday October 9 Lecture 2
 Math Programming Background Monday October 16 Lecture 3
 Convex Optimization Monday October 23 Lecture 4
 Maximum Cut Monday November 6 Lecture 5
 Spectral Partitioning Monday November 13 Chapter 2 from these notes by Luca Trevisan
 TSP Basics Monday November 20 Lecture 7            Homework 1            Solutions
 TSP + Convex Combinations Friday 13h30-15h00 F116 November 24 Lecture 8
 Randomized LP Rounding: Max-Sat Friday 14h00-15h30 F116 December 8 Lecture 9
 Randomized LP Rounding: Set Cover Friday 15h45-17h15 F116 December 8 Lecture 10
 ATSP + Hoffman Circulation Theorem Monday December 11 Lecture 11
 Review Monday December 18                             Homework 2            Solutions
 Final Exam Friday January 26                             Final Exam              Solutions

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