AMS Bookstore LOGO amslogo
AMS TextbooksAMS Applications-related Books
Randomization Methods in Algorithm Design
Edited by: Panos Pardalos and Sanguthevar Rajasekaran, University of Florida, Gainesville, FL, and José Rolim, University of Geneva, Switzerland
A co-publication of the AMS and DIMACS.

DIMACS: Series in Discrete Mathematics and Theoretical Computer Science
1999; 318 pp; hardcover
Volume: 43
ISBN-10: 0-8218-0916-4
ISBN-13: 978-0-8218-0916-7
List Price: US$84
Member Price: US$67.20
Order Code: DIMACS/43
[Add Item]

Request Permissions

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, 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.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1-7 were co-published with the Association for Computer Machinery (ACM).


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
Powered by MathJax

  AMS Home | Comments:
© Copyright 2014, American Mathematical Society
Privacy Statement

AMS Social

AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia