Approximation Algorithms for Combinatorial Optimisation
The School of Mathematical Sciences of Queen Mary University of London invite applications for a PhD project commencing in September 2019. The deadline for applications is 23 August 2019.
This project will be supervised by Dr. Justin Ward.
This project concerns the rigorous, mathematical analysis of practical algorithms for hard combinatorial optimisation problems.
Combinatorial optimisation problems involve selecting the best collection of items that satisfy some property; for example: the cheapest set of edges that form a spanning tree in an underlying graph, or the cheapest tour that visits some set of cities exactly once. While many optimisation problems arising in practice are NP-hard to solve optimally, it is often possible to design efficient algorithms that guarantee almost optimal solutions. The study of such so-called “approximation algorithms” thus involves a finer-grained hierarchy for studying the difficulty of NP-hard problems.
The project will focus on the general area of approximation algorithm, allowing for many possible directions, such developing new algorithms and rigorous analyses for problems related to submodular optimisation, clustering, facility location, or network design. These problems are motivated by concrete concerns from machine learning and operational research, and so the project might also consider new theoretical results for distributed, parallel, or streaming models of computation. Applicants with some background in the study of algorithms, theoretical computer science, discrete mathematics, or optimisation are especially encouraged to apply.
The application procedure is described on the School website. For further inquiries please contact Dr. Justin Ward at [Email Address Removed].
This project is eligible for full funding, including support for 3.5 years’ study, additional funds for conference and research visits and funding for relevant IT needs.
The School of Mathematical Sciences is committed to the equality of opportunities and to advancing women’s careers. As holders of a Bronze Athena SWAN award we offer family friendly benefits and support part-time study. Further information is available here. We strongly encourage applications from women as they are underrepresented within the School.
We particularly welcome applicants through the China Scholarship Council Scheme.
How good is research at Queen Mary University of London in Mathematical Sciences?
FTE Category A staff submitted: 34.80
Research output data provided by the Research Excellence Framework (REF)
Click here to see the results for all UK universities