Table of Contents

Preface. Contributing Authors. Volume I. 1. Random Sampling: Sorting and Selection; D. Krizanc, S. Rajasekaran. 2. Simplified Analysis of Randomized Algorithms for Searching, Sorting, and Selection; M.T. Goodrich, R. Tamassia. 3. Concentration of Measure for Randomized Algorithms: Techniques and Analysis; D. Dubhashi, S. Sen. 4. Randomization in Graph Optimization Problems: A Survey; D.R. Karger. 5. The Delay Sequence Argument; A. Ranade. 6. Randomized Algorithms for Geometric Optimization Problems; P.K. Agarwal, S. Sen. 7. Randomized Geometry Algorithms for Coarse Grained Parallel Computers; Xiaotie Deng. 8. A Randomized Approach to Robot Path Planning Based on Lazy Evaluation; R. Bohlin, L.E. Kavraki. 9. The Power of Two Random Choices: A Survey of Techniques and Results; M. Mitzenmacher, A.W. Richa, R. Sitaraman. 10. Randomized Techniques for Modelling Faults and Achieving Robust Computing; S.E. Nikoletseas, P.G. Spirakis. 11. Randomized Communication in Radio Networks; B.S. Chlebus. Index. Preface. Contributing Authors. Volume II. 12. A Guide to Concentration Bounds; J. Díaz, J. Petit, M. Serna. 13. Bounded Error Probabilistic Finite State Automata; A. Condon. 14. Communication Protocols - An Exemplary Study of the Power of Randomness; J. Hromkovic. 15. Property Testing; D. Ron. 16. The Random Projection Method; S. Vempala. 17. Error Estimates for Indirect Measurements: Randomized vs. Deterministic Algorithms for `Black-Box' Programs; V.Kreinovich, R. Trejo. 18. Derandomization in Combinatorial Optimization; A. Srivastav. 19. Derandomizing Complexity Classes; P.B. Miltersen. Index.

Promotional Information

Springer Book Archives