UBC Combinatorial Optimization CPSC 536S, Winter term 2, 2019

Course Outline

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.

Instructor

Bruce Shepherd Email: fbrucesh@cs.ubc.ca Webpage: bshepherd.ca Office hours: Tuesday 2:15-3:15 (ICICS X839) or even better this term (Winter 2019), just set up an appointment.

Lectures

Time: Monday and Wednesday at 13:30-15:00 Hugh Dempster Paviliion 101

Teaching Assistant

Mehrdad Ghadiri Office hours: TBA

Grading

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)

Assignments

What we've done so far

Week 1.

Monday

Polyhedra Approach for Solving Generic Combinatorial Optimization Problems.

Background reading:

Wednesday

Week 2.

Monday

The Branching Algorithm.

Background reading:

Wednesday

Week 3.

Monday

Wednesday

Week 4.

Monday

Wednesday

In-class Quiz

Week 5.

Monday

Wednesday

Week 6.

Monday

Wednesday

Week 7.

Reading Break. Assignment 2 Due Tues Feb 26.

Week 8.

Monday (Feb. 25)

Wednesday

Week 9.

Monday (March 4)

Wednesday

Week 10.

Monday (March 11)

Wednesday

Week 11.

Monday (March 18)

Wednesday

Week 12.

Monday (March 25)

Wednesday

Week 13.

Monday (April 1)

Wednesday

Week 13.

Monday (April 8)

Wednesday