Lecturer: Oleg Pikhurko

Term(s): Term 2

Status for Mathematics students: List A (MA252 is for 2nd years, MA352 for 3rd years provided MA252 has not been taken in a previous year).

Commitment: 30 lectures.

Assessment: 100% 2 hour exam

Formal registration prerequisites: None

Assumed knowledge: None

Useful background:

• MA241 Combinatorics
• CS137 Discrete Mathematics & its Applications 2
• CS260 Algorithms

Synergies: This module complements the following:

• MA241 Combinatorics
• MA4J3 Graph Theory

Leads to: The following modules have this module listed as assumed knowledge or useful background:

• MA4M4 Topics in Complexity Science
• MA4J5 Structures of Complex Systems

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, etc. We will also discuss "intractible" (e.g. NP-hard) problems.

Main Reference

• D. Du, P. Pardalos, X. Hu, & W. Wu, Introduction to Combinatorial Optimization, Springer 2022. E-book available through the Warwick Library; click the link.

Other Resources:

• W.J. Cook, William H. Cunningham, W. Pulleybank, & A. Schrijver, Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics, 1998.
• B. Korte & J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 6th Edition, 2018. E-book available through the Warwick Library; click the link.
• J Lee, A First Course in Combinatorial Optimization, Cambridge University Press, 2010.
• C.H. Papadimitriou & K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.
• L.A. Wolsey & G.L Nemhauser, Integer and Combinatorial Optimization, Wiley 1999.

Additional Resources