Skip to main content Skip to navigation

MA252 Combinatorial Optimisation

Lecturer: Vadim Lozin

Term(s): Term 2

Status for Mathematics students: List A for mathematics

Commitment: 30 lectures.

Assessment: 2 hour exam

Prerequisites: No formal prerequisites. Students who have taken CS126 Design of Information Structures, CS137 Discrete Mathematics and its Applications 2, MA241 Combinatorics or CS260 Algorithms will find it helpful, but no background from these modules will be assumed.

Leads To: This module may be useful for students interested in taking MA241 Combinatorics, MA3J2 Combinatorics II or MA4J3 Graph Theory, but it is not a formal prerequisite for them.

Content: The focus of combinatorial optimisation is on finding the "optimal" object (i.e. an object that maximises or minimises a particular function) from a finite set of mathematical objects. Problems of this type arise frequently in real world settings and throughout pure and applied mathematics, operations research and theoretical computer science. Typically, it is impractical to apply an exhaustive search as the number of possible solutions grows rapidly with the "size" of the input to the problem. The aim of combinatorial optimisation is to find more clever methods (i.e. algorithms) for exploring the solution space.

This module provides an introduction to combinatorial optimisation. Our main focus is on several fundamental problems arising in graph theory and algorithms developed to solve them. These include problems related to shortest paths, minimum weight spanning trees, matchings, network flows, cliques, colourings and matroids. We will also discuss "intractible" (e.g. NP-hard) problems.

Main Reference:

Other Resources:

Additional Resources

Archived Pages: 2012 2014 2015 2016 2017