DIMACS: Series in Discrete Mathematics and Theoretical Computer Science 1999; 318 pp; hardcover Volume: 43 ISBN10: 0821809164 ISBN13: 9780821809167 List Price: US$84 Member Price: US$67.20 Order Code: DIMACS/43
 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 17 were copublished with the Association for Computer Machinery (ACM). Readership Graduate students and research mathematicians working in computer science, engineering, and operations research. Table of Contents  R. D. Barve, E. F. Grove, and J. S. Vitter  Simple randomized Mergesort on parallel disks
 R. Battiti, A. Bertossi, and R. Rizzi  Randomized greedy algorithms for the hypergraph partitioning problem
 G. Cooperman and G. Havas  Elementary algebra revisited: Randomized algorithms
 O. Goldreich  Combinatorial property testing (a survey)
 J. Gu  Randomized and deterministic local search for SAT and scheduling problems
 K. Jansen  An approximation scheme for scheduling of malleable parallel tasks
 D. S. Kim  Blocking behaviors of broadcast switching networks in random traffics
 S. L. Martins, P. M. Pardalos, M. G. C. Resende, and C. C. Ribeiro  Greedy randomized adaptive search procedures for the Steiner problem in graphs
 L. McShine and P. Tetali  On the mixing time of the triangulation walk and other Catalan structures
 J. Mockus, A. Mockus, and L. Mockus  Bayesian approach for randomization of heuristic algorithms of discrete programming
 M. Molloy, B. Reed, and W. Steiger  On the mixing rate of the triangulation walk
 I. Pak  When and how \(n\) choose \(k\)
 S. Rajasekaran  Computing on optical models
 A. Sahai and S. Vadhan  Manipulating statistical difference
 A. Srinivasan  A survey of the role of multicommodity flow and randomization in network design and routing
 T. V. Theodosopoulos  Some remarks on the optimal level of randomization in global optimization
