Title | Advances in Randomized Parallel Computing [electronic resource] / edited by Panos M. Pardalos, Sanguthevar Rajasekaran |
---|---|
Imprint | Boston, MA : Springer US, 1999 |
Connect to | http://dx.doi.org/10.1007/978-1-4613-3282-4 |
Descript | XXVI, 287 p. online resource |
1 Optimal Bounds on Tail Probabilities: A Study of an Approach -- 1.1 Introduction -- 1.2 Bounding Tail Probabilities with the Laplace Transform -- 1.3 When only the Mean is given: The Hoeffding Bound -- 1.4 When the Mean and the Variance are given: A Simple Proof of the Bennett Bound -- 1.5 When the First n Moments are Given: A Glimpse of the General Theory -- 1.6 An Application: Improved Bounds for the List Update Problem -- References -- 2 Parallelism in Comparison Problems -- 2.1 Introduction -- 2.2 Selection -- 2.3 Merging -- 2.4 Sorting -- 2.5 Conclusions -- References -- 3 Random Sampling -- 3.1 Introduction -- 3.2 Preliminaries -- 3.3 Partitioning I: Sorting -- 3.4 Partitioning II: List Ranking -- 3.5 Pruning I: Selection -- 3.6 Pruning II: Row maxima of monotone matrices -- 3.7 Pruning III: Graph Connected Components -- 3.8 Other examples -- 3.5 Bibliographic Notes -- References -- 4 Randomized Algorithms on the Mesh -- 4.1 Introduction -- 4.2 Preliminaries -- 4.3 Routing on the mesh -- 4.4 Sorting on the mesh -- 4.5 Selection on the mesh -- References -- 5 Efficient Randomized Algorithms -- 5.1 Introduction -- 5.2 Preliminaries -- 5.3 Randomized Routing -- 5.4 Randomized Selection -- 5.5 Randomized Sorting -- 5.6 Randomized PRAM Emulation -- 5.7 Selection and Sorting Schemes for Processing Large Distributed Files -- 5.8 Conclusions -- References -- 6 Ultrafast Randomized Parallel Algorithms for Spanning Forests -- 6.1 Introduction -- 6.2 Uitrafast Parallel Algorithms -- 6.3 Dense Instances -- 6.4 Ultrafast Algorithms for Spanning Forests -- 6.5 Open Problems and Further Research -- References -- 7 Parallel Randomized Techniques for Some Fundamental Geometric Problems -- 7.1 Introduction -- 7.2 Preliminaries and Definitions -- 7.3 The Use of Randomization in Computational Geometry -- 7.4 Applications to Fundamental Geometric Problems -- 7.5 Summary -- References -- 8 Capturing the Connectivity of High-Dimensional Geometric Spaces -- 8.1 Introduction -- 8.2 Basic Probabilistic Roadmap Planner -- 8.3 Other Sampling Strategies -- 8.4 Roadmap Coverage -- 8.5 Roadmap Connectedness -- 8.6 Current and Future Work -- Appendix: A. Proof of Theorem 1 -- Appendix: B. Proof of Theorem 2 -- Appendix: C. Proof of Theorem 3 -- Appendix: D. Proof of Theorem 4 -- References -- 9 Randomized Parallel Prefetching and Buffer Management -- 9.1 Introduction -- 9.2 Definitions -- 9.3 Read-Once Reference Strings -- 9.4 Read-Many Reference Strings -- 9.5 Concluding Remarks -- References -- 10 DFA Problems -- 10.1 Introduction -- 10.2 Membership Problem -- 10.3 Containment and Equivalence Problems -- 10.4 Ranking and Related Problems -- 10.5 Coarsest Partition Problems -- 10.6 Automata Testing Problems -- 10.7 Conversion from Regular Expression to NFA -- 10.8 Applications -- 10.9 Open Problems -- References -- 11 LAPACK90 -- 11.1 Introduction -- 11.2 Interface Blocks for LAPACK 77 -- 11.3 Interface Blocks for LAPACK 90 -- 11.4 Code of LAPACK90 Routines -- 11.5 LAPACK90 Documentation -- 11.6 LAPACK90 Test Programs -- 11.7 LAPACK90 User Callable Routines -- References -- Appendix: A, Generic Interfaces -- A.1 LAPACK77 Generic Interface Blocks -- A.2 LAPACK90 Generic Interface Blocks -- Appendix: B, Interface Subroutines -- B.1 LA_GESV and LA_GETRI subroutines -- B.2 Auxiliary Routines -- Appendix: C -- C.1 Documentation of LA_GESV -- Appendix: D -- D.1 The LA_GESV test results -- Appendix: E -- E.1 LAPACK90 User Callable Routines