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.