AF: EAGER: Probabilistic Considerations in the Analysis of Algorithms

AF：EAGER：算法分析中的概率考虑

• 批准号: 1555599
• 负责人: ALAN FRIEZE
• 金额: $ 10万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1555599&HistoricalAwards=false
• 关键词: AF; EAGER; Probabilistic; Considerations; Analysis

One of the main uses for computers is to solve large computational problems of a discrete nature, for example to find ways of optimally routing vehicles to make deliveries within minimum time. To be useful, the amount of computing time needed to solve the problem must be small. Unfortunately, many, if not most of the problems of this nature tend to be of a class for which there is no algorithm that can finish quickly for all problem instances. On the other hand, these problems have to be tackled and it has been noted that algorithms tend to do better than the worst-case scenario might suggest.Integer Programming is a framework within which many of these problems can be described. The PI will conduct research on the average performance of algorithms for these problems. The aim is twofold. First, the PI wants to explain, in terms of probability, why the average performance is much better than the worst case. Second, the PI will seek ways to practically exploit the ''friendly'' nature of typical problems, thus leading to more efficient algorithms for Integer Programming.The related problem of Linear Programming has been a spectacular success for mathematics. The Simplex Algorithm and more recent Interior Point Method have enabled us to solve huge linear programs. Integer Programs are superficially similar to Linear Programs and one approach to solving them is through polyhedral methods. We try to approximate the convex hull of the integer solutions and then apply Linear Programming. This has led to the study of Polyhedral Combinatorics. The PI proposes to study Polyhedral Combinatorics within a probabilistic framework. For example, the PI will try to determine the expected number of Gomory cuts needed to solve a pure Integer Program. This will require a combination of probabilistic, geometric, and algorithmic ideas in order to be successful.

计算机的主要用途之一是解决离散性质的大型计算问题，例如找到优化车辆路线以在最短的时间内进行交付的方法。为了有用，解决问题所需的计算时间必须很短。不幸的是，许多（如果不是大多数）这种性质的问题往往属于没有算法可以快速完成所有问题实例的类别。另一方面，这些问题必须得到解决，并且人们已经注意到，算法往往比最坏情况可能暗示的效果更好。整数规划是一个可以描述许多此类问题的框架。 PI将对这些问题的算法的平均性能进行研究。目的是双重的。首先，PI 想要从概率角度解释为什么平均性能比最坏情况好得多。其次，PI 将寻求方法来实际利用典型问题的“友好”性质，从而产生更有效的整数规划算法。线性规划的相关问题在数学上取得了巨大的成功。单纯形算法和最近的内点法使我们能够解决巨大的线性规划。整数规划表面上与线性规划相似，解决它们的一种方法是通过多面体方法。我们尝试近似整数解的凸包，然后应用线性规划。这导致了多面体组合学的研究。 PI 建议在概率框架内研究多面体组合学。例如，PI 将尝试确定解决纯整数规划所需的预期 Gomory 割次数。这需要概率、几何和算法思想的结合才能成功。