Lecture Notes from CSC2411 Spring 2005

 


Assignments Assignment 1
Assignment 2
Assignment 3
Assignment 4

Course Description

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 Ellipsoid algorithm.
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.

Students will be expected to have a basic knowledge of algorithms and linear algebra.

Reading

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.

Grading

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.

Syllabus !-->

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 interior-point 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. Geomans-Williamson Maxcut algorithm. Karger Motwani Sudan approxiamted colouring algorithm. Lovasz theta function. Lecture notes by Kevin Yuen.