## CSC 2411H Linear and Semidefinite Programming and Combinatorial Optimization

### Spring 2009

Lecture: Thursday 11-13, HA 410 Avner Magen by appointment (SF 2301B, 946-8672). Siavosh Benabbas

## Course Description

The course deals with pervasive optimization problems such as Linear Programming and Semidefinite Programming. It has two main parts

### A. Structural study of linear Programs and semidefinite programs, and how to solve them efficiently

• basic geoemetry and linear algebra related to Linear Programming.
• simplex-method
• duality theorem (leading to Von Neumann's minmax principle) and complimentary slackness.
• ellipsoid algorithm. separation oracles.
• semidefinite programming as an extension of linear programming
• interior point algorithms

### B. Use of Linear Programming and semidefinte programming in solving (approximating) combinatorial problems

• problems with LP relaxation leading to the exact optimum.
• problem where the LP/SDP relaxation only leads to approximated solutions.
• integrality gaps
• rounding, probabilistic roundings, iterative rounding, primal dual methods.
• lift and project type methods for LP/SDP relaxations
• lower bounds to LP/SDP type approaches

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

There is no real text for the course. Here is a list for recommended ones. The first two below are reserved and can be borrowed for only 24 hours from the Engineering library.

• Understanding and Using Linear Programming by MAtousek and Gartner (2006)
• Linear Progrmaming by Karloff (1991)
• Combinatorial Optimization, Algorithms and complexity by Papadimitriou and Steiglitz.
• Linear Programming by Chvatal (1983)
• Theory of Linear and Integer Programming, Schrijver (1993)
• Geometric Algorithms and Combinatorial Optimization, by Grotschel, Lovasz and Schrijver (1988)
• Approximation Algorithms by Vazirani (2001)
• there are also previous lecture notes from similar courses that were taught in 2005 and 2007.

assignment 1
assignment 2
assignment 3
assignment 4

## Announcements

Date Announcement(s)
19/5

final grades were submitted to office (at the beginning of the month actually). Exams are available with Eliabeth Ribeiro,SF2301D

5/4

EXAM. Monday April 20th, 11:00-2:00. Location BA3008.

5/4

Small corrections were applied in question 4. The version was updated 6/4 Monday morning.

3/4

2/4

Tutorial on Friday 3/4 10AM in BA3008.

11/3

Tutorial on Friday 13/3 10AM in BA3008.

11/3

19/2

Assignment 1 is marked and can be picked up from my office.

12/2

12/2

Tutorial tomorrow Firday the 13th, 10AM. New location: SF3207.

31/1

I have added one question to assignment 1. Check the final version above.

26/1

Class this week (29/1) will be delivered by the TA Siavosh as I will be away

20/1

IMPORTANT CORRECTION: in my previous message I announced that tutorial will be today, Tue 20/1 at 4. I was unaware that there is a theory grad course (CSC2410) which some students here take. So we are down to FRIDAY 23/1 at 10. Room: BA3008.

15/1
We need to find a time for tutorials. The times I suggest are:
-Tuesday 2
-Tuesday 4
-Wednesday 12
-Wednesday 4
-Thursday 3
-Friday 10
There will be 5-6 tutorials throguht the term. The first (basics of linear algebra) will be next week. Please let me know which of the times will not work for you.