9505167 Steele Abstract The aim of this project is to build a deeper understanding of the stochastic behaviors present in some of the central problems of Euclidean combinatorial optimization. Examples of problems that are to be investigated include the stochastic models of the traveling salesman problem, the minimum spanning tree problem, and several of their related approximations. The more specific objectives of the project include (1) further development of the distribution theory for the traveling salesman problem and minimal spanning tree problem, (2) more extensive development of Talagrand's theory of configuration functions, (3) refined understanding of the tail behavior of the increasing subsequence functional, and (4) development of the basic limit theory for functionals associated with non-optimal heuristics. The methods that will be used in this investigation include Talagrand's isoperimetric theory, Talagrand's theory of irregularity of distribution, the theory of subadditive Euclidean functionals, the general efficiency theory for statistical estimation, and the theory of vector quantization. Each of these tools is of considerable importance in its own right, and the expectation is that useful insight will be gained into the strengths and weaknesses of these tools through the study of the concrete problems of probabilistic combinatorial optimization. The interface of probability theory and optimization has experienced remarkable growth over the last five years, and this development has had substantial impact on both theoretical computer science and the practice of algorithm development. The aim of this project is to build a deeper understanding of the information and assistance that probability can provide in some difficult and important problems of computation. In particular, the project aims to develop probability theory that helps describe the behavior of several important quantities in the theory of combinatorial optimization, a subj ect that studies the minimization and maximization of functions that are defined very large finite sets. The more specific objectives of the project include development of a distribution theory for the length of the shortest path through a large number of points whose locations are determined by a probability distribution, and the development of the basic probability for some of the most important approximation methods of optimization theory.
