The Cut Polytope and Related Convex Bodies

点击翻译按钮获取中文摘要

Optimisation is concerned with methods for finding the 'best' option when one is faced with a huge range of possible options. More formally, it deals with maximising (or minimising) a function of some decision variables, subject to various constraints. The proposed project is concerned with an optimisation problem called the max-cut problem. It is concerned with partitioning a graph into two pieces so as to maximise the number of edges crossing from one piece to the other.As well as being an interesting problem in its own right, the max-cut problem also has many applications, for example in computer science, telecommunications, statistics, theoretical physics, computational biology, and branches of mathematics such as combinatorics, graph theory and the theory of metric spaces.The max-cut problem is difficult to solve both in theory and practice. Although there are good heuristic methods available which can obtain good quality solutions to large instances, the state-of-the-art exact methods are capable of solving instances with only up to around 100 vertices to proven optimality.The main goals of the proposed project are to deepen our understanding of the max-cut problem, to devise methods which are capable of solving larger instances to optimality, and to implement these methods as computer software. To do this, a theoretical study will have to be made of a certain geometric object known as the cut polytope, and certain related geometric objects.