DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Forty Three
TITLE: "Randomization Methods in Algorithm Design"
EDITORS: Panos Pardalos and Sanguthevar Rajasekaran

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.

PREFACE


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.

TABLE OF CONTENTS


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 how n choose k
    I. 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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.