This is jointly funded project (between the Theory of Computing Program, CCR and Probability Program, DMS), that started under CCR-92-25008, ``Probabilisitic Considerations in the Analysis of Algorithms''. Probalilistic considerations arise in the analysis of algorithms in at least two important ways: (1) In a randomized algorithm the outcomes of random events are used to determine the progress of the algorithm. Randomization is now a standard tool of the computational scientist; (2) A second area of consideration is when the problem instances come from some probability distribution, and one wants to understand the average performance of a particular algorithm, which is often far better than its worst case. Under this previous grant, CCR-92-08597, probabilistic and algorithmic issues were explored in such areas as: (a) sampling, (b) path problems, (c) counting, (d) heuristics for bisection/k-cut of weighted graphs,(d) greedy algorithms, (e) computational biology, (f) complexity of determining polyhedra from its faces, (g) hypergraphs, and(h) probabilistic combinatorics. This project explores problems in both areas. In (1) the area of randomized algorithms, the problems examined include: (1a) random walks on graphs; (1b) approximation algorithms; and (1c) learning and routing problems. In (2) the area of probabilistic analysis, the problems studied include: (2a) greedy algorithms; (2b) in computational biology, sequencing by hybridization and physical mapping reconstruction for DNA; and (2c) some geometric problems.***
