Lecturer: Jonathan Noel

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, CS137, MA241 or CS260 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, MA3J2 or MA4J3, 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 linear programming and algorithms developed to solve them. These include problems related to shortest paths, minimum weight spanning trees, linear programming, matchings, network flows, cliques, colourings, dynamic programming, multicommodity flows and matroids. We will also discuss "intractible" (e.g. NP-hard) problems.

Preliminary Schedule:

A preliminary schedule for the 2018-2019 edition of the module can be found here.

Main Reference:

• A. Schrijver, A Course in Combinatorial Optimization, Unpublished Lecture Notes, 2017. Available for free through the link.¹

Other Resources:

• A. Bondy and U. S. R. Murty, Graph Theory with Applications, Elsevier, 1976. Available through the link.
• B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 6th Edition, 2018. E-book available through the Warwick Library; click the link.
• A. Schrijver, Advanced Graph Theory and Combinatorial Optimization, Unpublished Lecture Notes. Available for free through the link.¹
• 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.
• D. Bertsimas, J. N. Tsitsiklis, Introduction to linear optimization, Athena Scientific, c1997

¹Permission to use these unpublished lecture notes for this module was generously granted by the author, A. Schrijver.

Additional Resources

Archived Pages: 2012 2014 2015 2016 2017

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