Skip to main content
School of Mathematical Sciences

Connections between optimisation and extremal combinatorics

Supervisor: Dr Justin Ward

Project description:

This project concerns the mathematical interplay between combinatorial constructions and the worst-case analysis of optimisation algorithms.

As an example of this interplay between analysis of optimisation algorithms and construction of extremal combinatorial objects, we consider the set packing problem with bounded set sizees, which is a natural generalisation of the classical matching problem. There, it is known that the worst-case inputs for state-of-the-art approximation algorithms can be constructed from regular graphs of high girth, and inapproximability results for these problems are based on constructions involving disperser graphs. From the other direction, the analysis of iterated rounding algorithms for linear programs has led to partial progress towards confirming the F\"uredi-Kahn-Seymour conjecture, and new connections to the Lov\'asz theta function. Finally, results including the sunflower lemma and constructions from Ramsey theory have recently been used to derive improved guarantees for several optimisation algorithms, breaking long-standing barriers. The aim of this project is to study these connections in more detail, starting initially with set packing problems, in order to develop new guarantees or further understanding of the limits of common heuristic approaches.

Further information:

How to apply

Entry requirements

Fees and funding

Back to top