Probability and Statistics Applied to the Theory of Algorithms.
PENNSYLVANIA STATE UNIV UNIVERSITY PARK DEPT OF STATISTICS
Pagination or Media Count:
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. Blands 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
- Numerical Mathematics
- Statistics and Probability