Some of the hardest computational problems have been successfully attacked through the use of probabilistic algorithms, which have an element of randomness to them. Concepts from the field of probability are also increasingly useful in analyzing the performance of algorithms, broadening our understanding beyond that provided by the worst-case or average-case analyses.
This book surveys both of these emerging areas on the interface of the mathematical sciences and computer science. It is designed to attract new researchers to this area and provide them with enough background to begin explorations of their own.
Table of Contents
|2 Simulated Annealing||17-30|
|3 Approximate Counting Via Markov Chains||31-38|
|4 Probabilistic Algorithms for Speedup||39-52|
|5 Probabilistic Algorithms for Defeating Adversaries||53-64|
|6 Pseudorandom Numbers||65-86|
|7 Probabilistic Analysis of Packing and Related Partitioning Problems||87-108|
|8 Probability and Problems in Euclidean Combinatorial Optimization||109-130|
|9 Probabilistic Analysis in Linear Programming||131-148|
|10 Randomization in Parallel Algorithms||149-160|
|11 Randomly Wired Multistage Networks||161-174|
|12 Missing Pieces, Derandomization, and Concluding Remarks||175-178|
The National Academies Press and the Transportation Research Board have partnered with Copyright Clearance Center to offer a variety of options for reusing our content. You may request permission to:
For most Academic and Educational uses no royalties will be charged although you are required to obtain a license and comply with the license terms and conditions.
For information on how to request permission to translate our work and for any other rights related query please click here.
For questions about using the Copyright.com service, please contact:
Copyright Clearance Center
22 Rosewood Drive
Danvers, MA 01923
Tel (toll free): 855/239-3415 (select option 1)
Loading stats for Probability and Algorithms...