Parallel comparison algorithms for approximation problems

DOI10.1007/BF01206355MaRDI QIDQ808727zbMATH OpenOpenAlexFDO

Authors Noga Alon, Yossi Azar

Publication date 1991

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01206355

zbMATH Keywords

approximate sortingapproximation problemsapproximate mergingapproximate maximum problemparallel comparison tree

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Distributed algorithms (68W15)

Recommendations

• Finding an Approximate Maximum
• Parallel selection
• scientific article; zbMATH DE number 559227
• Parallel algorithms for partitioning sorted sets and related problems
• Parallel complexity of sorting problems

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Finding an Approximate Maximum
• Finding the maximum, merging, and sorting in a parallel computation model
• Graphs whose every transitive orientation contains almost every relation
• Parallel Sorting with Constant Time for Comparisons
• Parallel selection
• Parallel sorting
• Parallelism in Comparison Problems
• Routing, merging, and sorting on parallel models of computation
• Searching, Merging, and Sorting in Parallel Computation
• Sorting and Merging in Rounds
• Sorting and Selecting in Rounds
• Sorting in one round
• Sorting, Approximate Sorting, and Searching in Rounds
• Tight Comparison Bounds on the Complexity of Parallel Sorting

Cited in

(10)

• Finding an approximate median with high probability in constant parallel time
• A comparative analysis of the convergence regions for different parallel affine projection algorithms
• scientific article; zbMATH DE number 4178740 (Why is no real title available?)
• Transforming comparison model lower bounds to the parallel-random-access-machine
• scientific article; zbMATH DE number 1294384 (Why is no real title available?)
• scientific article; zbMATH DE number 4015931 (Why is no real title available?)
• Strategy-accurate parallel Buchberger algorithms
• scientific article; zbMATH DE number 697771 (Why is no real title available?)
• scientific article; zbMATH DE number 3947421 (Why is no real title available?)
• The acyclic orientation game on random graphs

This page was built for publication: Parallel comparison algorithms for approximation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808727)