Probability and Statistics Applied to the Theory of Algorithms

This grant has the central aim of exploring when, and how, probability is useful in the theory of algorithms. Most of the problems reviewed have their origins in the area of Euclidean Combinatorial Optimization, which might be operationally defined as the theory that has evolved out of the study Euclidean traveling salesman problem (TSP), the minimal spanning tree problem, and the minimal matching problem. Probability enters the study of such problems by two different paths. One path calls on exogenous randomization in the course of a genuine probabilistic algorithm. This path is of increasing importance in many areas, and on an elementary level is well illustrated by the method of simulated annealing. A second path of considerable importance calls on the introduction of stochastic models for the problem inputs. One then uses probability theory to understand as deeply as possible the behavior of the associated objective functions. This understanding is used subsequently to guide algorithm design.