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
What we've done so far
Week 1.
Monday
Polyhedra Approach for Solving Generic Combinatorial Optimization Problems.
Background reading:
- For graph theory: Bondy and Murty
- Primer on Complexity Theory.
Wednesday
- Some examples: matchings an Euler tours, min cost paths and negative cycles, minimum cost subgraphs with connectivity requirements, TSP.
- Intro to the Minimum Arborescence and Maximum Branching Problems.
Week 2.
Monday
The Branching Algorithm.
Background reading:
- Korte-Vygen.
Wednesday
- Correctness of the Branching Algorithm.
- Edmonds Arborescence Packing Theorem; the Uncrossing Lemma.
- Thomassen's Conjecture.
Week 3.
Monday
- Algorithm for packing arborescences. (Reading: Korte-Vygen). Weighted Dijoin Packing Conjecture.
- Intro to Convexity. Separating hyperplane theorem. Multi-coloured simplices.
Wednesday
- Polyhedral basics. Characteristic (recession) cones, affine hull, dimension
- Polyhedral Decomposition Theorem.
- Swift intro to LP Duals and Complementary Slackness
Week 4.
Monday
- Characterizations of polyhedral faces (and vertices).
- Intro to Polyhedral Combinatorics. Valid inequalities for stable set polytope.
Wednesday
- Polyhedral Combinatorics. Stable set polytopes of bipartite graphs (and generalizations).
- Separation and Optimization.
In-class Quiz
Week 5.
Monday
- Totally Unimodular Matrices.
- Total Dual Integrality (TDI).
- Examples of Network Matrices.
Wednesday
- Intro to Matroids. The Greedy Algorithm.
- Examples of Matroids (Graphic, Partition, Laminar, Linear, Gammoids...).
Week 6.
Monday
- Matroid Structure. Submodularity, circuits, unique circuit property.
Wednesday
- Facets and Defining Systems.
- The Matroid Polytope Theorem.
- Introduction to Matroid Intersection Theorem. Examples.
Week 7.
Reading Break. Assignment 2 Due Tues Feb 26.
Week 8.
Monday (Feb. 25)
- Matroid Intersection.
Wednesday
- Matroid Projection Theorem.
- Quiz.
Week 9.
Monday (March 4)
- Matroid Partitioning.
- Min Cost Arborescence Algorithm via Packing (Bock/Fulkerson).
Wednesday
- Integer Duals.
- Dominants.
- Gomory-Hu Trees.
Week 10.
Monday (March 11)
- Analysis of Gomory-Hu Algorithm.
- Dijoins and Lucchesi-Younger Theorem.
Wednesday
- Box-Integrality of Submodular Flow Polyhedron.
Week 11.
Monday (March 18)
- Packing dijoins. Woodall's Conjecture.
- Blockers and Lehman's Theorem.
Wednesday
- Intro to Matchings.
- Non-bipartite Matching Algorithm.
Week 12.
Monday (March 25)
- Weighted Matching Algorithm.
Wednesday
- Analaysis of the Weighted Matching Algorithm
- T-joins and their Applications
Week 13.
Monday (April 1)
- Algorithm for T-joins.
- Christofides 1.5-approximation for Metric TSP
- Subtour Elimination (Held-Karp) Formulation and the 4/3 Conjecture
Wednesday
- Robust Network Design
- Proof of the Virtual Private Network (VPN) Theorem