AF: EAGER: Probabilistic Considerations in the Analysis of Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.