The Cut Polytope and Related Convex Bodies

切割多面体和相关凸体

基本信息

批准号：
EP/D072662/1
负责人：
Adam Letchford
金额：
$ 48.61万
依托单位：
Lancaster University
依托单位国家：
英国
项目类别：
Fellowship
财政年份：
2006
资助国家：
英国
起止时间：
2006 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FD072662%2F1
关键词：
Cut Polytope 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.

优化涉及在面对各种可能的选项时找到“最佳”选项的方法。更正式的是，它涉及受到各种限制的某些决策变量的最大化（或最小化）函数。拟议的项目与称为最大切割问题的优化问题有关。它与将图表分成两块有关，以最大程度地提高一个从一个部分到另一个部分的边缘数量。以及最大的问题本身就是一个有趣的问题，最大切割问题也有许多应用，例如在计算机科学，电信，统计，统计学，统计学，统计，理论物理学，计算生物学，计算生物学和诸如数学界的跨越理论，综合理论，综合理论，跨越理论，跨越理论，综合理论。在理论和实践中。尽管有良好的启发式方法可以为大型实例获得高质量的解决方案，但最先进的精确方法只能求解具有大约100个顶点的实例以证明最佳性。拟议项目的主要目标是加深我们对最大切割问题的理解，以使能够求解更大的实例以求解更大的实例以实现这些方法，以实现这些方法，并将这些方法用于这些软件。为此，必须对某个几何对象和某些相关的几何对象进行理论研究。