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 DAAL03-91-G-0110 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