## 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