Details of Grant 

EPSRC Reference:	EP/D072662/1
Title:	The Cut Polytope and Related Convex Bodies
Principal Investigator:	Letchford, Professor A
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Management Science
Organisation:	Lancaster University
Scheme:	Advanced Fellowship
Starts:	01 August 2006	Ends:	31 July 2011	Value (£):	381,481
EPSRC Research Topic Classifications:	Artificial Intelligence Mathematical Aspects of OR
EPSRC Industrial Sector Classifications:	Communications
Related Grants:
Panel History:	Panel Date Panel Name Outcome 23 Mar 2006 Mathematics 2006 Fellowships Panel Deferred 24 Apr 2006 Mathematics Fellowships Interview Panel Deferred
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.lancs.ac.uk