Hardcover ISBN:  9780821809167 
Product Code:  DIMACS/43 
List Price:  $100.00 
MAA Member Price:  $90.00 
AMS Member Price:  $80.00 
eBook ISBN:  9781470440015 
Product Code:  DIMACS/43.E 
List Price:  $94.00 
MAA Member Price:  $84.60 
AMS Member Price:  $75.20 
Hardcover ISBN:  9780821809167 
eBook: ISBN:  9781470440015 
Product Code:  DIMACS/43.B 
List Price:  $194.00 $147.00 
MAA Member Price:  $174.60 $132.30 
AMS Member Price:  $155.20 $117.60 
Hardcover ISBN:  9780821809167 
Product Code:  DIMACS/43 
List Price:  $100.00 
MAA Member Price:  $90.00 
AMS Member Price:  $80.00 
eBook ISBN:  9781470440015 
Product Code:  DIMACS/43.E 
List Price:  $94.00 
MAA Member Price:  $84.60 
AMS Member Price:  $75.20 
Hardcover ISBN:  9780821809167 
eBook ISBN:  9781470440015 
Product Code:  DIMACS/43.B 
List Price:  $194.00 $147.00 
MAA Member Price:  $174.60 $132.30 
AMS Member Price:  $155.20 $117.60 

Book DetailsDIMACS  Series in Discrete Mathematics and Theoretical Computer ScienceVolume: 43; 1999; 318 ppMSC: Primary 03; 90; 68
This volume is based on proceedings held during the DIMACS workshop on Randomization Methods in Algorithm Design in December 1997 at Princeton. The workshop was part of the DIMACS Special Year on Discrete Probability. It served as an interdisciplinary research workshop that brought together a mix of leading theorists, algorithmists and practitioners working in the theory and implementation aspects of algorithms involving randomization.
Randomization has played an important role in the design of both sequential and parallel algorithms. The last decade has witnessed tremendous growth in the area of randomized algorithms. During this period, randomized algorithms went from being a tool in computational number theory to finding widespread applications in many problem domains.
Major topics covered include randomization techniques for linear and integer programming problems, randomization in the design of approximate algorithms for combinatorial problems, randomization in parallel and distributed algorithms, practical implementation of randomized algorithms, derandomization issues, and pseudorandom generators. This volume focuses on theory and implementation aspects of algorithms involving randomization. It would be suitable as a graduate or advanced graduate text.
Copublished with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were copublished with the Association for Computer Machinery (ACM).
ReadershipGraduate students and research mathematicians working in computer science, engineering, and operations research.

Table of Contents

Chapters

Simple randomized Mergesort on parallel disks

Randomized greedy algorithms for the hypergraph partitioning problem

Elementary algebra revisited: Randomized algorithms

Combinatorial property testing (a survey)

Randomized and deterministic local search for SAT and scheduling problems

An approximation scheme for scheduling of malleable parallel tasks

Blocking behaviors of broadcast switching networks in random traffics

Greedy randomized adaptive search procedures for the Steiner problem in graphs

On the mixing time of the triangulation walk and other Catalan structures

Bayesian approach for randomization of heuristic algorithms of discrete programming

On the mixing rate of the triangulation walk

When and how $n$ choose $k$

Computing on optical models

Manipulating statistical difference

A survey of the role of multicommodity flow and randomization in network design and routing

Some remarks on the optimal level of randomization in global optimization


RequestsReview Copy – for publishers of book reviewsAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Requests
This volume is based on proceedings held during the DIMACS workshop on Randomization Methods in Algorithm Design in December 1997 at Princeton. The workshop was part of the DIMACS Special Year on Discrete Probability. It served as an interdisciplinary research workshop that brought together a mix of leading theorists, algorithmists and practitioners working in the theory and implementation aspects of algorithms involving randomization.
Randomization has played an important role in the design of both sequential and parallel algorithms. The last decade has witnessed tremendous growth in the area of randomized algorithms. During this period, randomized algorithms went from being a tool in computational number theory to finding widespread applications in many problem domains.
Major topics covered include randomization techniques for linear and integer programming problems, randomization in the design of approximate algorithms for combinatorial problems, randomization in parallel and distributed algorithms, practical implementation of randomized algorithms, derandomization issues, and pseudorandom generators. This volume focuses on theory and implementation aspects of algorithms involving randomization. It would be suitable as a graduate or advanced graduate text.
Copublished with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were copublished with the Association for Computer Machinery (ACM).
Graduate students and research mathematicians working in computer science, engineering, and operations research.

Chapters

Simple randomized Mergesort on parallel disks

Randomized greedy algorithms for the hypergraph partitioning problem

Elementary algebra revisited: Randomized algorithms

Combinatorial property testing (a survey)

Randomized and deterministic local search for SAT and scheduling problems

An approximation scheme for scheduling of malleable parallel tasks

Blocking behaviors of broadcast switching networks in random traffics

Greedy randomized adaptive search procedures for the Steiner problem in graphs

On the mixing time of the triangulation walk and other Catalan structures

Bayesian approach for randomization of heuristic algorithms of discrete programming

On the mixing rate of the triangulation walk

When and how $n$ choose $k$

Computing on optical models

Manipulating statistical difference

A survey of the role of multicommodity flow and randomization in network design and routing

Some remarks on the optimal level of randomization in global optimization