Randomization Methods in Algorithm Design
About this Title
Panos Pardalos, University of Florida, Gainesville, FL, Sanguthevar Rajasekaran, University of Florida, Gainesville, FL and José Rolim, University of Geneva, Geneva, Switzerland, Editors
Publication: DIMACS Series in Discrete Mathematics and Theoretical Computer Science
Publication Year: 1999; Volume 43
ISBNs: 978-0-8218-0916-7 (print); 978-1-4704-4001-5 (online)
MathSciNet review: MR1660775
MSC: Primary 68-06; Secondary 68Q25, 90-06
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.
Graduate students and research mathematicians working in computer science, engineering, and operations research.
Table of Contents
- 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