# MA252 Combinatorial Optimisation

**Lecturer****: **Vadim Lozin

**Term(s):** Term 2

**Status for Mathematics students:** List A for Mathematics

**Commitment:** 30 lectures.

**Assessment:** 100% 2 hour exam

**Formal registration prerequisites: **None

**Assumed knowledge: **None

**Useful background: **

**Synergies: **This module complements the following:

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

**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:**

- B. Korte and J. Vygen,
*Combinatorial Optimization: Theory and Algorithms*, Springer, 6th Edition, 2018. E-book available through the Warwick Library; click the link.

**Other Resources:**

- A. Bondy and U. S. R. Murty,
*Graph Theory with Applications*, Elsevier, 1976. Available 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.