scientific article; zbMATH DE number 1302200
Chernoff boundscombinatorial optimizationcomplexity classesdepth first searchmatching problemsmaximal independent set problemsminimum cost spanning treesnetwork flow problemspacket routingparallel randomized algorithmsshortest paths problemssortingsurvey
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)
The aim of the paper is to survey basic parallel randomized algorithms for some discrete problems. In particular, the author presents algorithms used for sorting, packet routing, shortest paths problems, matching problems, depth first search, minimum cost spanning trees, maximal independent set problems and network flow problems. The paper begins with a preliminary section which provides the basic notations and definitions adopted in the rest of the paper (parallel models of computing, randomized algorithms, Chernoff bounds, complexity classes NC, RNC). The algorithms for sorting on PRAM, Mesh and Hypercube are described in brief and their properties -- run time complexity and the number of processors -- are presented in the tables. Section ``Packet Routing and all following sections are already written in the usual mathematical style. A routing algorithm on \(n\times n\) Mesh with \((2+\varepsilon)n\) runtime for any fixed \(\varepsilon\geq 1/\log n\) is described. For routing on undirected graphs with \(n\) vertices and \(m\) edges an algorithm is presented with \(O(\sqrt n)\) run time and \(m\log n\) processors. The section devoted to matching problems recalls namely important Tutte's result found in the 1947. A randomized algorithm using Tutte matrix for perfect matching in a graph is presented. This section also contains several useful lemmas concerning computation complexity and equivalence between some routing problems and perfect matching in a graph. The section ``Luby's Method is devoted to an important randomized technique for optimization problems. This method is presented by describing an efficient algorithm for Maximal Independent Set problem. In the section ``Randomization and approximation the authors focus on the MAX FLOW problem for networks. They prove several lemmas and a theorem which states the MAX FLOW problem belong to the complexity class RNC (polylogarithmic run time, polynomial number of processors and randomized algorithms). This well-written paper is a valuable survey of some basic randomization techniques for efficient parallel algorithms and may be highly recommended. For the entire collection see [Zbl 0914.90002].
- An introduction to parallelism in combinatorial optimization
- Optimal parallel randomized algorithms for sparse addition and identification
- Tight Analysis of Parallel Randomized Greedy MIS
- Probabilistic Parallel Algorithms for Sorting and Selection
- scientific article; zbMATH DE number 4047072 (Why is no real title available?)
- Randomized parallel algorithms
- The Random Adversary: A Lower-Bound Technique for Randomized Parallel Algorithms
- scientific article; zbMATH DE number 1163099 (Why is no real title available?)
- scientific article; zbMATH DE number 934538 (Why is no real title available?)
- scientific article; zbMATH DE number 1419214 (Why is no real title available?)
- Parallel Combinatorial Optimization with Decision Diagrams
- An optimal parallel algorithm for generating combinations
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247467)
