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 NP-hard 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 Simplex-Method,
and then study the first polynomial algorithm to the problem, namely the
Another, less algorithmic path we will take is studying the the concept of duality and the duality-theorem 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 game-theory, Yao's minmax principle and the "primal-dual" algorithmic paradigm. We will then discuss positive-semi-definite programming and the way it can be solved using the Ellipsoid algorithm.
The last part of the course will deal with methods of approximating NP-hard 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, Springer-Verlag 2001.
A related course taught this term is CSC 2421H : "Approximation Algroithms" by Allan Borodin.
There will be 4-5 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 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 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 11: Solvability of SDP by Ellipsoid method and interior-point methods. Relaxations of LP. Unimodularity condition. Konig Theorem from LP duality and from unimodularity. Lecture notes by Vinod Nair.