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.
To learn some of the classical techniques and algorithms in
Combinatorial Optimizations with a wide range of applications.
CMPUT 304 or strong undergraduate background in theoretical computer
science and mathematics. You must also have basic knowledge of graph
There is no required text; lecture notes will be provided.
Here is a list of references:
- 3-volume book by A.
Optimization: Polyhedra and Efficiency , Springer-Verlag,
Optimization: Algorithms and Complexity, by Christos H.
Papadimitriou, Kenneth Steiglitz, Dover Publications, 1998.
First Course in Combinatorial Optimization, by J. Lee, Cambridge
Algorithms, by Vijay V. Vazirani, Springer, 2004.
- 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,
- 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
- 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
- Lecture 21, 22: Vertex Cover, Set Cover, TSP, Multiway Cut
- Lecture 23, 24: Max-SAT (Randomized Algorithm, Biased Coin, LP
- Lecture 25, 26: Max-Cut, semidefinite programming
Template for course notes.
- 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)
This is a theory course (no programming involved). There will be 3 or 4
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
Scribe notes for each week are
due the next Monday at noon. Scribe notes must be typed in LaTeX using
the template provided above.
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.
Questions? Send email to me ...
- 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
- Submodular functions
- Approximation Algorithms (TSP, vertex cover)
- Primal/Dual method
- Iterative method
- Semidifinite Programming and applications