University of Toronto
Department of Computer Science

CSC 2411H
Linear and Semidefinite Programming and Combinatorial Optimization

Spring 2009

 

Lecture: Thursday 11-13, HA 410

Instructor: Avner Magen

Office hours: by appointment (SF 2301B, 946-8672).

Tutor: 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.

    Reading

    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.

    Assignments

    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

    Assignment 4 uploaded.

    2/4

    Tutorial on Friday 3/4 10AM in BA3008.

    11/3

    Tutorial on Friday 13/3 10AM in BA3008.

    11/3

    Assignment 3 uploaded.

    19/2

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

    12/2

    Assignment 2 uploaded.

    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.