Combinatorial Optimisation: 20222023
Lecturer  
Degrees  Schedule C1 (CS&P) — Computer Science and Philosophy Schedule B1 (CS&P) — Computer Science and Philosophy Schedule C1 — Computer Science Schedule B1 — Computer Science Schedule C1 — Mathematics and Computer Science 
Term  Michaelmas Term 2022 (16 lectures) 
Overview
This course is an introduction to combinatorial optimisation (with focus on algorithms). It will introduce ideas and techniques underlying many standard algorithms taught in introductory firstyear and secondyear algorithms courses and go beyond.This is a new part B course, in 20222023 also offered to part C students.
Learning outcomes
Learning standard combinatorial algorithms, including algorithms for cuts and matchings in graphs. Understand the concept of submodular functions and their structural and algorithmic properties. Understand the concept of matroids and their structural and algorithmic properties.Prerequisites
Algorithms, on the level covered by the compulsory firstyear course Design and Analysis of Algorithms and the compulsory secondyear course Algorithms and Data Structures.
Discrete Mathematics and Graph Theory, on the level of the two algorithms courses above.
Computational Complexity, on the level covered by the optional Part A/B course, is not required by might be handy.
Synopsis

[1 lecture] Introduction. Introduction. Redblue algorithm for MST.

[2 lectures] Cuts. Mincut. GomoryHu trees. Multiwaycut. Minkcut.

[1 lecture] TSP. Christofides' algorithm. Steiner tree.

[3 lectures] Matchings. Matchings. Edmonds’ blossom algorithms.

[2 lectures] Tjoins. Tjoins. Minimum weight Tjoin. Applications.

[4 lectures] Submodularity. Sumobular functions. Unconstrained minimisation. Odd minimisation. Symmetric minimisation. Cardinality maximisation. Unconstrained maximisation.

[3 lectures] Matroids. Matroids. Greedy algorithm. Matroid intersection.
Syllabus
A generic algorithm for minimumspanning trees. A combinatorial algorithm (not based on flows) for minimum cuts in undirected graphs. GomoryHu trees for (s,t)mincuts in undirected graphs. Multiwaycuts and minkcuts. Traveling salesman problem. An algorithm for the maximum weight matching problem in general graphs and applications. Submodular functions and their optimisation: unconstrained minimisation, symmetric minimisation, odd minimisation, unconstrained maximisation, and maximisation with a cardinality constraint. Matroids. An algorithm for matroid intersection.
Reading list
Primary text: Lecture notes prepared by the lecturer.
Supplementary list:
 Cook, Cunningham, Pulleyblank, and Schrijver. Combinatorial Optimization.
 Korte and Vygen. Combinatorial Optimization: Theory and Algorithms.
 Lee. A First Course in Combinatorial Optimization.
 Nemhauser and Wolsey. Integer and Combinatorial Optimization.
 Papadimitriou and Steiglitz. Combinatorial Optimization: Algorithms and Complexity.
 Schrijver: Combinatorial Optimization.
Feedback
Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.