
Accession Number : ADA295805
Title : Probability and Statistics Applied to the Theory of Algorithms.
Descriptive Note : Final rept.,
Corporate Author : PENNSYLVANIA STATE UNIV UNIVERSITY PARK DEPT OF STATISTICS
Personal Author(s) : Steele, J. M.
PDF Url : ADA295805
Report Date : 07 APR 1995
Pagination or Media Count : 8
Abstract : The work reviewed here is centered around the tools and results of probability theory that contribute to the theory of algorithms, especially the theory of combinatorial optimization. The reviewed cites sixteen articles and three Ph.d. theses that were supported in part by ARO Grant DAAL0391G0110 during the period of May 1991 to October 1993, including the optional third year (so the present report necessarily overlaps with the report filed in October 1992 that covered the first two years of the grant). The work surveyed includes work on the objective method which led to the the resolution with David Aldous of R. Bland's conjecture that the sum of the squares of the edges of the minimal spanning tree of a random sample from the unit square converges to a constant as the sample size goes to infinity, work with R. Stine on symbolic stochastic calculus, the NAS Panel Report Probability and Algorithms, work with T. L. Snyder on the worst case behavior of the traveling salesman problem, and work with Jun Gao on the spacefilling curve heuristics, as well as other work on probability and its relation to the theory of algorithms. (AN)
Descriptors : *ALGORITHMS, *STOCHASTIC PROCESSES, *PROBABILITY, OPTIMIZATION, QUEUEING THEORY, RANDOM VARIABLES, CONVERGENCE, HEURISTIC METHODS, COMBINATORIAL ANALYSIS, DISTRIBUTION FUNCTIONS, CURVES(GEOMETRY).
Subject Categories : Numerical Mathematics
Statistics and Probability
Distribution Statement : APPROVED FOR PUBLIC RELEASE