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切割的预期数量。这将需要概率、几何和算法思想的结合才能成功。