Lecture Notes from CSC2411 Spring 2005 
This course deals with the problem of optimizing linear
function in linear or other convex domains, and application to the
theory of algorithms, mainly for the approximation of NPhard problems.
The heart of the course will be linear programming.
We will first investigate the algebraic and geometric foundations of this
object, and then turn to study the algorithmic approaches to solve it.
We will present the famous and commonly used SimplexMethod,
and then study the first polynomial algorithm to the problem, namely the
Ellipsoid algorithm.
Another, less algorithmic path we will take is studying the the concept
of duality and the dualitytheorem in LP. This is possibly the most
fundamental theorem in the theory of optimization, and provides an extremely
efficient tool to many optimization problems. We will discuss few of the
applications of the theorem, Von Neumann minmax principle in gametheory,
Yao's minmax principle and the "primaldual" algorithmic paradigm.
We will then discuss positivesemidefinite programming and the
way it can be solved using the Ellipsoid algorithm.
The last part of the
course will deal with methods of approximating NPhard problems using
the convex optimization tools we established in the earlier parts.
There is no real text for the course. The closest to one is Papadimitriou and Steiglitz' book "Combinatorial Optimization, Algorithms and complexity" Dover edition, 1998. Others usefull books are Chvatal, Linear Programming, Freeman, 1983; Schrijver, Theory of Linear and Integer Programming, Wiley 1986;
M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization,
Springer, 1988; Vazirani, Approximation Algorithms, SpringerVerlag 2001.
A related course taught this term is CSC 2421H : "Approximation Algroithms" by Allan Borodin.
There will be 45 problem sets that will make 60% of the grade. The final
will make the remaining 40%. Students will also be expected to scribe lecture notes for some
classes during the semester, and for a reasonably good job in that, the lowest homework score will be dropped.
Here
are templates for writing scribes in latex. You will need this class file and you might want to use bib file, eps file and jpg file (the last two are definitely not a must).
This is the pdf version of that file (lecture0). A first draft of the notes is expected in the following lecture.
Week 1: Optimization, convex optimization, linear programming (LP). Lecture notes by Victor Glazer. 

Week 2: Different forms of LP. The algebraic objects behind LP, Basic Feasible Solutions. Lecture notes by Graham Taylor. 

Week 3: Geometric aspects of LP. Simplex algorithm. Lectrue notes by Adam Tenenbaum. 

Week 4: Simplex algorith contd. Different pivot rules. Exponential time lower bound for the simplex algorithm. Lecture notes by Chuan Wu. 

Week 5: Smoothed analysis. Randomized combinaotrial algorithms that run in subexponential time (Seidel, Kalai, Matousek Sharir Welzl). Linear Programming Duality Lecture notes by Mea Wang. Here is a good survey by Michael Godwasser. 

Week 6: LP Duality contd. Complementary slackness. Farkas Lemma. von Neumann minmax principle. Lecture notes by Pixing Zhang. 

Week 7: von Neumann minimax theorem, Yao's minimax Principle, Ellipsoid Algorithm Lecture notes by Xuming He. 

Week 8: Ellipsoid algorithm contd. The concept of membership and separation oracles. Lecture notes by Shizhong Li. 

Week 9: Interior point method : Ye's Primal Dual I.P. algorithm (here is a good survey by L. Tuncel; and perhaps even better, here is a minicourse in Twente on I.P methods that may be more useful). Lecture notes by Vincent Cheung. 

Week 10: Semidefinite Programming (SDP). Formulation, relation to Vector Programming, duality. A survey by Robert M. Freund, and one by Michel X. Goemans Lecture notes by Mike Jamieson. 

Week 11: Solvability of SDP by Ellipsoid method and interiorpoint methods. Relaxations of LP. Unimodularity condition. Konig Theorem from LP duality and from unimodularity. Lecture notes by Vinod Nair. 

Week 12: Integrality gaps, rounding, randomized rounding. Lecture notes by Matei David. 

Week 13: SDP relaxations. GeomansWilliamson Maxcut algorithm. Karger Motwani Sudan approxiamted colouring algorithm. Lovasz theta function. Lecture notes by Kevin Yuen. 