UBC Combinatorial Optimization CPSC 536S, Winter term 2, 2019
We give a thorough introduction to the field of combinatorial optimization. The course includes an introduction to polyhedral combinatorics which is then a background 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: email@example.com Webpage: bshepherd.ca Office hours: Tuesday 3:00-4:00 (ICICS X839) or by appointment.
Time: Monday and Wednesday at 13:30-15:00 Hugh Dempster Paviliion 101
Mehrdad Ghadiri Office hours: TBA
Course grades will be (tentatively) based upon: 3 assignments (15% each), 3 quizzes (10% each), a take-home final exam (20%), and class participation! (5%).
Quiz Dates (all in class. last Wednesdays of January, February, March)
What we've done so far
Polyhedra Approach for Solving Generic Combinatorial Optimization Problems.
Several examples. The Minimum Arborescence Problem.
The Branching Algorithm.
Correctness of the Branching Algorithm. Intro to Convexity and Polyhedral Combinatorics (?)