Skip to main content

Combinatorial Optimization

Overview

  • Credit value: 15 credits at Level 7
  • Coordinator and lecturer: Steven Noble
  • Assessment: two short, problem-based assignments (20%) and a three-hour examination (80%)

Module description

This module provides an introduction to a variety of optimization problems which can be solved using combinatorial techniques, including the underlying mathematics ensuring correctness of techniques and applications.

Indicative module syllabus

  • The greedy algorithm and matroids: examples of greedy algorithms for spanning trees and the travelling salesman problem; characterisation of when the greedy algorithm succeeds in terms of matroids
  • Matching problems: the Hungarian algorithm for maximum weight matchings and applications such as Tutte’s theorem on the existence of a matching, T-joins and postman problem; geometric matching
  • Maximum flows: maximum flow-minimum cut theorem, Ford-Fulkerson algorithm and applications such as the elimination of sportsteams problem; related problems/algorithms such as push-relabel flows, the minimum cut problem and Gomory-Hu trees
  • Minimum cost flows: network simplex method for the minimum cost flow problem and applications such as rectilinear graph drawing

Learning objectives

By the end of this module, you will be able to:

  • understand and use mathematical techniques
  • understand a range of results and several topics in mathematics
  • comprehend and evaluate conceptual and abstract material
  • devise rigorous mathematical proofs
  • understand and apply mathematical reasoning in several different areas of mathematics.