The Probabilistic Method Yields Deterministic Parallel Algorithms

A method is provided for converting randomized parallel algorithms into deterministic parallel algorithms. The approach is based on a parallel implementation of the method of conditional probabilities. Results obtained by applying the method to the set balancing problem, lattice approximation, edge-coloring graphs, random sampling, and combinatorial constructions are presented. The general form in which the method of conditional probabilities is applied sequentially is described. The reason why this form does not lend itself to parallelization are discussed. The general form of the case for which the method of conditional probabilities can be applied in the parallel context is given. >

Authors

• Rajeev Motwani 0001
• Joseph Naor
• Moni Naor

Keywords

• Parallel algorithms
• Lattices
• Geometry
• Ink
• Computer science
• Contracts
• Cloning
• Approximation algorithms
• Color
• Sampling methods
• Parallel Algorithm
• Random Variables
• Small Variations
• Parallelization
• Conditional Probability
• Independent Set
• Estimation Problem
• Sample Space
• Input Size
• Good Point
• Probability Space
• Least Significant Bit
• Binary Search
• Lattice Points
• Hypergraph
• Good Color
• Vertex Cover
• Number Of Processors
• Edge Coloring
• Input Instance
• Linear Programming
• Random Sampling