Discrete Mathematics and Theoretical Computer Science

TITLE: "Randomization Methods in Algorithm Design"

EDITORS: Panos Pardalos and Sanguthevar Rajasekaran

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the
AMS Bookstore and
order directly from there.
DIMACS ** does not** distribute or sell these books.

This volume is based on proceedings held during the DIMACS workshop on Randomization Methods in Algorithm Design December 12-14, 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, de-randomization issues, and pseudo-random generators. This volume focuses on theory and implementation aspects of algorithms involving randomization. It would be suitable as a graduate or advanced graduate text.

Foreword xi Preface xiii Simple randomized Mergesort on parallel disks R. D. Barve, E. F. Grove, and J. S. Vitter 1 Randomized greedy algorithms for the hypergraph partitioning problem R. Battiti, A. Bertossi, and R. Rizzi 21 Elementary algebra revisited: Randomized algorithms G. Cooperman and G. Havas 37 Combinatorial property testing (a survey) O. Goldreich 45 Randomized and deterministic local search for SAT and scheduling problems J. Gu 61 An approximation scheme for scheduling of malleable parallel tasks K. Jansen 109 Blocking behaviors of broadcast switching networks in random traffics D. S. Kim 123 Greedy randomized adaptive search procedures for the Steiner problem in graphs S. L. Martins, P. M. Pardalos, M. G. C. Resende, and C. C. Ribeiro 133 On the mixing time of the triangulation walk and other Catalan structures L. McShine and P. Tetali 147 Bayesian approach for randomization of heuristic algorithms of discrete programming J. Mockus, A. Mockus, and L. Mockus 161 On the mixing rate of the triangulation walk M. Molloy, B. Reed, and W. Steiger 179 When and hownchoosekI. Pak 191 Computing on optical models S. Rajasekaran 239 Manipulating statistical difference A. Sahai and S. Vadhan 251 A survey of the role of multicommodity flow and randomization in network design and routing A. Srinivasan 271 Some remarks on the optimal level of randomization in global optimization T. V. Theodosopoulos 303

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on October 28, 1998.