Combinatorial Optimisation: 20242025
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 2024 (20 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.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.

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

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

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

[4 lectures] Matroids. Matroids. Basic properties and constructions. Greedy algorithm. Unweighted and weighted 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.
Taking our courses
This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses
Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.