Accession Number : ADA259956


Title :   Probability and Statistics Applied to the Theory of Algorithms


Descriptive Note : Final rept. 1 May 1991-31 May 1992


Corporate Author : WHARTON SCHOOL PHILADELPHIA PA DEPT OF STATISTICS


Personal Author(s) : Steele, J M


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a259956.pdf


Report Date : Dec 1992


Pagination or Media Count : 14


Abstract : 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.


Descriptors :   *ALGORITHMS , *PROBABILITY , *SYSTEMS APPROACH , INPUT , ANNEALING , PATHS , GRANTS , MATCHING , TREES , OPTIMIZATION , MODELS , THEORY


Subject Categories : Statistics and Probability


Distribution Statement : APPROVED FOR PUBLIC RELEASE