Welcome to the last week of this course! In Lecture 20 we will wrap up our treatment of semidefinite programming by presenting a celebrated result by Goemans and Williamson, which showed that semidefinite programming can be used to solve difficult combinatorial problems. In the last lecture we will walk through the whole course, highlight the important topics, and prepare for the exam by discussing some old exam or similar questions. Let me know if there is anything in particular that you’d like to feature in this last class!

Learning outcomes

  • Understand how semidefinite programming can be used to solve combinatorial problems.

Tasks and Materials

  • The lecture notes and problem sheets are available in their respective sections. In particular, the Lectures section now contains a complete set of all the lecture notes in one document. The exam from last year has been published with solutions in the Exams section.

Further reading

  • Bernd Gärtner, Jiří Matoušek. Approximation Algorithms and Semidefinite Programming. Springer, 2012

Literature

  1. Bernd Gärtner, Jiří Matoušek. Approximation Algorithms and Semidefinite Programming. Springer, 2012
  2. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.