Mini-Course on LP and SDP Rounding (IRIF, Paris, Spring 2020)




Course Outline

Lecture Schedule

 Lecture I February 13 LP rounding: Triangle transversals (using complementary slackness), Bin packing (using extreme point structure)                           
 Lecture II February 14 LP rounding: Randomized set-cover rounding, Applications to directed graph theory                           
 Lecture III February 18 SDP rounding: Max-Cut, Coloring 3-colorable graphs                   
 Lecture IV February 20 SDP rounding: Finding large stable sets, Max-k-cut                   

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