FindAPhD Weekly PhD Newsletter | JOIN NOW FindAPhD Weekly PhD Newsletter | JOIN NOW

Machine learning for NP-hard minimization problems


   Department of Computer Science

This project is no longer listed on FindAPhD.com and may not be available.

Click here to search FindAPhD.com for PhD studentship opportunities
  Prof S Cox  No more applications being accepted  Funded PhD Project (Students Worldwide)

About the Project

The UKRI CDT in Artificial Intelligence, Machine Learning and Advanced Computing (AIMLAC) aims at forming the next generation of AI innovators across a broad range of STEMM disciplines. The CDT provides advanced multi-disciplinary training in an inclusive, caring and open environment that nurture each individual student to achieve their full potential. Applications are encouraged from candidates from a diverse background that can positively contribute to the future of our society. 

The UK Research and Innovation (UKRI) fully-funded scholarships cover the full cost of tuition fees, a UKRI standard stipend of £15,921 per annum and additional funding for training, research and conference expenses. The scholarships are open to UK and international candidates.

Closing date for applications is 12 February 2022. For further information on how to apply please click here and select the "UKRI CDT Scholarship in AIMLAC" tab.

Project Overview

Given a flat, circular pizza and a group of N friends, how should one cut the pizza with the least amount of cutting so that everyone gets a piece of the same size? This somewhat improbable question highlights a more general class of problems associated with seeking least perimeter or least area partitions of two- or three-dimensional objects respectively. Such problems arise naturally in the study of the geometric structure of foams and emulsions and, like the better-known Travelling Salesman problem, are generally NP-hard.

Re-framing the question as determining the least-perimeter partition of a circle into N regions of equal area, some progress in determining the optimal solutions has been made for small N. There are proofs for N=1, 2, 3, conjectured solutions for N up to 42 [1], and evidence that defects tend to cluster towards the periphery of the partition at N over about 5,000 [2].

There are also many generalisations: partitioning regular polygons, the surface of various three dimensional shapes such as the sphere and the torus, or three-dimensional space itself. This latter question is known as the Kelvin problem, for which a solution has been sought for almost 150 years.

We therefore have training data and a well-defined optimization function. The goal of the PhD project would be to develop a machine learning algorithm for such problems, with the aim of presenting solutions for large N with a high degree of confidence, which might inspire mathematical proofs, and possibly new solutions to the Kelvin problem.


References

[1] S.J. Cox and E. Flikkema (2010) The minimal perimeter for N confined deformable bubbles of equal area. Elec. J. Combinatorics 17:R45. See also users.aber.ac.uk/sxc/two_d_clusters.html
[2] S.J. Cox, F. Morgan and F. Graner (2013) Are large perimeter-minimizing two-dimensional clusters of equal-area bubbles hexagonal or circular? Proc. Roy. Soc A 469: 20120392.

Search Suggestions
Search suggestions

Based on your current searches we recommend the following search filters.

PhD saved successfully
View saved PhDs