Lecturer	Standa Živný
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 Schedule B1(M&CS) — Mathematics and Computer Science Michaelmas Term — MSc in Advanced 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 first-year and second-year 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 first-year course Design and Analysis of Algorithms and the compulsory second-year 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. Red-blue algorithm for MST.

• [2 lectures] Cuts. Min-cut. Gomory-Hu trees. Multiway-cut. Min-k-cut.

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

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

• [3 lectures] T-joins. T-joins. Minimum weight T-join. 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 minimum-spanning trees. A combinatorial algorithm (not based on flows) for minimum cuts in undirected graphs. Gomory-Hu trees for (s,t)-min-cuts in undirected graphs. Multiway-cuts and min-k-cuts. 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.