This page contains content from the 2017-2018 module. It will be updated soon for 2018-2019.

Lecturer: Vadim Lozin

Term(s): Term 2

Status for Mathematics students: List A for mathematics

Commitment: 30 lectures.

Assessment: 2 hour exam

Prerequisites: Basic knowledge of discrete mathematics could be helpful.

Leads To:

Content: Many complex everyday problems involve finding an optimal solution in a large, but finite, solution space. Combinatorial optimisation is concerned with the study of effective algorithms for solving such problems by cleverly exploring the solution space. Although many practical problems appear to be insurmountably hard (NP-complete), there are a vast number of problems that can be solved by effective (polynomial time) algorithms.

This module provides an introduction to combinatorial optimisation. In particular, we discuss various fundamental graph-theoretic algorithms. Among others we aim to cover, shortest path algorithms, minimum spanning trees, matching, coverings, network flows, cliques and colorings.

At the end of the course you are expected to have good understanding of various fundamental graph theoretic notions and algorithms. You should also appreciate constructive proofs in finite mathematics.

Books:
W.J. Cook, William H. Cunningham, W. R. Pulleybank, and A. Schrijver, Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics, 1998.
C.H. Papadimitriou and K. Steiglitz Combinatorial Optimization: Algorithms and Complexity Optimization: Algorithms and Complexity, Dover Publications, 1998.
Dimitris Bertsimas, John N. Tsitsiklis, Introduction to linear optimization, Athena Scientific, c1997
Bernhard Korte and Jens Vygen, Combinatorial Optimization: Theory and Algorithms, Springer (any edition)

Additional Resources

Year 1 regs and modules
G100 G103 GL11 G1NC

Year 2 regs and modules
G100 G103 GL11 G1NC

Year 3 regs and modules
G100 G103

Year 4 regs and modules
G103

Past Exams
Core module averages