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: firstname.lastname@example.org Webpage: bshepherd.ca Office hours: Tuesday 2:15-3:15 (ICICS X839) or even better this term (Winter 2019), just set up an 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%).
all in class. last Wednesdays of January, February, March
What we've done so far
Polyhedra Approach for Solving Generic Combinatorial Optimization Problems.
- 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.
The Branching Algorithm.
- Correctness of the Branching Algorithm.
- Edmonds Arborescence Packing Theorem; the Uncrossing Lemma.
- Thomassen's Conjecture.
- Algorithm for packing arborescences. (Reading: Korte-Vygen). Weighted Dijoin Packing Conjecture.
- Intro to Convexity. Separating hyperplane theorem. Multi-coloured simplices.
- Polyhedral basics. Characteristic (recession) cones, affine hull, dimension
- Polyhedral Decomposition Theorem.
- Swift intro to LP Duals and Complementary Slackness
- Characterizations of polyhedral faces (and vertices).
- Intro to Polyhedral Combinatorics. Valid inequalities for stable set polytope.
- Polyhedral Combinatorics. Stable set polytopes of bipartite graphs (and generalizations).
- Separation and Optimization.
- Totally Unimodular Matrices.
- Total Dual Integrality (TDI).
- Examples of Network Matrices.
- Intro to Matroids. The Greedy Algorithm.
- Examples of Matroids (Graphic, Partition, Laminar, Linear, Gammoids...).
- Matroid Structure. Submodularity, circuits, unique circuit property.
- Facets and Defining Systems.
- The Matroid Polytope Theorem.
- Introduction to Matroid Intersection Theorem. Examples.
Reading Break. Assignment 2 Due Tues Feb 26.
Monday (Feb. 25)
- Matroid Intersection.
- Matroid Projection Theorem.
Monday (March 4)
- Matroid Partitioning.
- Min Cost Arborescence Algorithm via Packing (Bock/Fulkerson).
- Integer Duals.
- Gomory-Hu Trees.
Monday (March 11)
- Analysis of Gomory-Hu Algorithm.
- Dijoins and Lucchesi-Younger Theorem.
- Box-Integrality of Submodular Flow Polyhedron.
Monday (March 18)
- Packing dijoins. Woodall's Conjecture.
- Blockers and Lehman's Theorem.
- Intro to Matchings.
- Non-bipartite Matching Algorithm.
Monday (March 25)
- Weighted Matching Algorithm.
- Analaysis of the Weighted Matching Algorithm
- T-joins and their Applications
Monday (April 1)
- Algorithm for T-joins.
- Christofides 1.5-approximation for Metric TSP
- Subtour Elimination (Held-Karp) Formulation and the 4/3 Conjecture
- Robust Network Design
- Proof of the Virtual Private Network (VPN) Theorem