UBC Combinatorial Optimization CPSC 536S, Winter term 1, 2022

Course Outline

We give a thorough introduction to the field of combinatorial optimization. The course follows the `polyhedral approach' to combinatorial optimization. We begin with an introduction to polyhedral combinatorics which is then the theme for designing algoirithms for combinatorial problems. We will sample topics from classical combinatorial optimization problems including minimum cost arborescence, maximum weight matching, T-joins, matroid intersection, perfect matrices and virtual private network problem. We also expect to devote some time to approximation algorithms for problems such as the travelling salesman problem and maximum cut.

The course will be more theoretically focused as opposed to numerical. Hence a reasonable mathematical background (say in linear algebra) is recommended.


Bruce Shepherd Email: fbrucesh@cs.ubc.ca Webpage: bshepherd.ca Office hours: Tuesday (1:30-3:00). Or by appointment (zoom or in-person possible).


Time: Monday and Wednesday at 1:00 - 2:30 Orchard Commons 4068

Teaching Assistant

Abner Turkieltaub Office hours: Wednesdays 11:30-12:30. Or by appointment (zoom or in-person possible)


Course grades will be based upon: 4 assignments (15% each); last assignment during exam period, 3 in-class quizzes (10% each), 2 in-class semi-surprise quizzes (5% each).

Quiz Dates.

last Wednesdays of September, October, November

What we've done so far

Week 1.


Polyhedra Approach for Solving Generic Combinatorial Optimization Problems.

Background reading:

Week 2.


A Combinatorial Min-Max Theorem for Shortest Paths. Detecting negative cycles in Undirected versus Directed networks.


Background reading:

Week 3.

Monday, September 19

No classes due to Queen's Funeral


Week 4.

Monday Sep 26

Wednesday, September 28

Week 5.

Monday Oct 3

Wednesday Oct 5

Week 6.

Monday Oct 10. Thanksgiving

Wednesday Oct 12

Week 7.

Monday Oct 17

Wednesday Oct 19

Week 8.

Monday Oct 24

Wednesday Oct 26

Week 9.

Monday Oct 31

Wednesday Nov 2

Week 10.

Monday Nov 7

Wednesday Nov 9

Week 11.

Monday Nov 14

Wednesday Nov 16

Week 12.

Monday Nov 21

Wednesday Nov 23

Week 13.

Monday Nov 28

Wednesday Nov 30

Week 14.

Monday Dec 5

Wednesday Dec 7