Optimization and Approximation (M1, Fall 2018)

Lecturer: Nicolas Bousquet
Teaching assistant: Johanna Seif and Dewi Sintiari

Textbooks:

• MIT course of Linear Programming

Lecture notes:

• Introduction to optimization
• Introduction to polytopes
• Simplex algorithm
• Initialization and termination
• Duality
• Dual solutions and many other things
• Integrality of polytopes
• Integrality gaps and Erdos Posa property
• Game Theory
• Linear programs for approximation algorithms (by Alantha Newman)
• Primal-Dual algorithms (by Alantha Newman)

Tutorial session:

• TD01 - problem
• TD02 - problem
• TD03 - problem
• TD04 - problem
• TD05 - problem
• TD06 - problem
• TD07 - problem
• TD08 - problem
• TD09 - problem
• TD10 - problem
• TD11 - problem
• TD12 - problem
• TD13 - problem
• TD14 - problem

Assignments:

• HW01 - problem
• HW02 - problem

N.b. Feel free to contact me if you need a solution!