Skip to main content

Combinatorial Optimisation:  2022-2023

Lecturer

Degrees

Schedule C1 (CS&P)Computer Science and Philosophy

Schedule B1 (CS&P)Computer Science and Philosophy

Schedule C1Computer Science

Schedule B1Computer Science

Schedule C1Mathematics and Computer Science

Schedule B1(M&CS)Mathematics and Computer Science

Michaelmas TermMSc in Advanced Computer Science

Term

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.

This is a new part B course, in 2022-2023 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 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.

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

  • [2 lectures] T-joins. T-joins. Minimum weight T-join. 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 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.

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.