CMPUT 675: Topics in Algorithms and Combinatorial Optimization

Fall 2009, NEW time and location: Tue and Thr 9:30-10:50:, in MEC 4-1.

Instructor: Mohammad R. Salavatipour

Purpose:

To learn some of the classical techniques and algorithms in
Combinatorial Optimizations with a wide range of applications.

Prerequisites:

CMPUT 304 or strong undergraduate background in theoretical computer
science and mathematics. You must also have basic knowledge of graph
theory.

Textbook:

There is no required text; lecture notes will be provided.

Here is a list of references:

- 3-volume book by A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency , Springer-Verlag, 2003.
- Combinatorial Optimization: Algorithms and Complexity, by Christos H. Papadimitriou, Kenneth Steiglitz, Dover Publications, 1998.
- A First Course in Combinatorial Optimization, by J. Lee, Cambridge University Press, 2004.
- Approximation Algorithms, by Vijay V. Vazirani, Springer, 2004.

Annoucnements:

- Oct 13: I have posted lecture notes 8,9 (but it still needs
editing). I have also posted the second assignment.

Notes for Lectures 10 and 11 will be posted later this week.

- Oct 1: Lecture notes 6,7 have been posted.

A good reference for some of the topics are the notes by Michel Goemans for similar courses taught at MIT: here, and here

- Sept 21: Assignment 1 has been posted below.

- Sept 14: Starting tomorrow (Sept 15), the lectures will be held
from 9:30-11:00 at MEC 4-1
(Tue/Thr).

- Please e-mail me with your preference regarding the time of
lecture (to move it to mornings or keep it in the current time slot).

- Lecture 1: Introduction, Cardinality bipartite matching (notes in PS and PDF)
- Lecture 2 and 3: Cardinality bipartite matching, weighted bipartite matching (notes in PS and PDF)
- Lecture 4 and 5: weighted bipartite matching, matching in general graphs (notes in PS and PDF)
- Lecture 6 and 7: Linear Programming, Simplex Algorithm (notes in PS and PDF)
- Lecture 8 and 9: Ellipsoid Method, Perfect Matching Polytope and TUM matrices (notes in PS and PDF)
- Lecture 10 and 11: Matching Polytope (general graphs), Max-flow Min-cut (notes in PS and PDF)
- Lecture 12 and 13: Min cost flow, Circulation, Matroids (in PDF)

- Lecture 14 and 15: Matroid optimization (notes in PS and PDF)
- Lecture 16 and 17: Matroid Intersections, MST polytope (notes in PS and PDF)
- Lecture 18 and 19: Uncrossing technique, MST, and Bounded Degree
Spanning Tree (notes in PS and PDF)

- Lecture 20: Bounded degree spanning tree, Approximation
Algorithms

- Lecture 21, 22: Vertex Cover, Set Cover, TSP, Multiway Cut
- Lecture 23, 24: Max-SAT (Randomized Algorithm, Biased Coin, LP rounding)
- Lecture 25, 26: Max-Cut, semidefinite programming

Template for course notes.

Assignments:

- NEW draft of Assignment 3 in PS and PDF format.

- Assignment 2 in PS and PDF
format (due date extended to Nov 3).

- Assignment 1 in PS and PDF format (Note the new due date)

Grading policy:

This is a theory course (no programming involved). There will be 3 or 4
assignment sets.

Also, each participant in the course is required to provide scribe
notes for one or two weeks of lectures. This is worth 10% of your
final mark.

Scribe notes for each week are
due the next Monday at noon. Scribe notes must be typed in LaTeX using
the template provided above.

Tentative syllabus:

Here is a a tentative list of some of the topics. Note that some of
these topics may not be covered or extra topics may be added.

- Preliminaries, basic definitions
- Cardinality bipartite matching, weighted bipartite matching (assignment problems)
- general matching
- polytopes, Linear Programming (LP), Geometry
- Solving LP's (Simplex, Ellipsoid)
- Max-Flow, Min-cut
- Matching Polytope, Path and flow polyhedra, total unimodularity
- Min-cost flow and circulations
- Matroids, Matroid optimization, Matroid intersection, Matroid union
- Submodular functions
- Arborescences,
- Approximation Algorithms (TSP, vertex cover)
- Primal/Dual method
- Iterative method
- Semidifinite Programming and applications