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.

• 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