Lecture Notes from CSC2411 Spring 2007

Week 6: Ellipsoid algorithm. Lecture notes by Svetlana Stolpner.

Week 7: Ellipsoid algorithm, cont. Lecture notes by Mohammad Sadoghi.

Week 8: Interior Point Method, Semi Definite Programming (SDP) Lecture notes by Sara Mostafavi.

Week 9: Semi Definite Programming (SDP), combinatorial optimization: approxiamtion algorithms through LP relaxation of Integer Program Lecture notes by Michael Mathioudakis.

Week 10: Exact relaxations, integrality gaps and rounding procedutes Lecture notes by Gerald Quon.

Week 11: Max-Sat relaxation. Primal Dual Schema Lecture notes by Sepand Mavandadi.

Week 12: SDP relaxations Lecture notes by Xinwei Gui.

Week 13 (I): Karger Motwani Sudan algorithm for colouring using SDP relaxation and Lovasz Theta function Lecture notes by Waqas ur Rehman.

Week 13(II): Lovasz Schrijver Lift and Project system (Guest lecture by Iannis Tourlakis) Lecture notes by Mathe Stephan.

See also the following surveys