AF: EAGER: Probabilistic Considerations in the Analysis of Algorithms

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

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.