Logo - springer
Slogan - springer

Mathematics | Handbook of Randomized Computing - Volume I/II

Handbook of Randomized Computing

Volume I/II

Series: Combinatorial Optimization, Vol. 9

Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolim, J. (Eds.)

2001, XXVII, 969 p.

Available Formats:
eBook
Information

Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.

You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.

After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.

 

ISBN 978-1-4615-0013-1

digitally watermarked, no DRM

The eBook version of this title will be available soon


learn more about Springer eBooks

add to marked items

Hardcover
Information

Hardcover version

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.

 
$99.00

(net) price for USA

ISBN 978-0-7923-6959-2

free shipping for individuals worldwide

The book title is in reprint. You can already preorder it.


add to marked items

Softcover
Information

Softcover (also known as softback) version.

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.

 
$99.00

(net) price for USA

ISBN 978-1-4613-4886-3

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days


add to marked items

  • About this book

The technique of randomization has been employed to solve numerous prob­ lems of computing both sequentially and in parallel. Examples of randomized algorithms that are asymptotically better than their deterministic counterparts in solving various fundamental problems abound. Randomized algorithms have the advantages of simplicity and better performance both in theory and often is a collection of articles written by renowned experts in practice. This book in the area of randomized parallel computing. A brief introduction to randomized algorithms In the analysis of algorithms, at least three different measures of performance can be used: the best case, the worst case, and the average case. Often, the average case run time of an algorithm is much smaller than the worst case. 2 For instance, the worst case run time of Hoare's quicksort is O(n ), whereas its average case run time is only O(nlogn). The average case analysis is conducted with an assumption on the input space. The assumption made to arrive at the O(n logn) average run time for quicksort is that each input permutation is equally likely. Clearly, any average case analysis is only as good as how valid the assumption made on the input space is. Randomized algorithms achieve superior performances without making any assumptions on the inputs by making coin flips within the algorithm. Any analysis done of randomized algorithms will be valid for all possible inputs.

Content Level » Research

Related subjects » Computational Science & Engineering - Mathematics

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.

Popular Content within this publication 

 

Articles

Services for this book

New Book Alert

Get alerted on new Springer publications in the subject area of Optimization.