Parallel comparison algorithms for approximation problems

DOI10.1007/BF01206355zbMath0732.68085OpenAlexW2067729110MaRDI QIDQ808727

Yossi Azar, Noga Alon

Publication date: 1991

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

approximation problemsapproximate sortingapproximate mergingapproximate maximum problemparallel comparison tree

Mathematics Subject Classification ID

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

Related Items (2)

Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ The acyclic orientation game on random graphs

Cites Work

• Unnamed Item
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Graphs whose every transitive orientation contains almost every relation
• Parallel selection
• Routing, merging, and sorting on parallel models of computation
• Sorting in one round
• Parallel sorting
• Searching, Merging, and Sorting in Parallel Computation
• Sorting and Selecting in Rounds
• Tight Comparison Bounds on the Complexity of Parallel Sorting
• Sorting, Approximate Sorting, and Searching in Rounds
• Finding an Approximate Maximum
• Finding the maximum, merging, and sorting in a parallel computation model
• Parallel Sorting with Constant Time for Comparisons
• Sorting and Merging in Rounds
• Parallelism in Comparison Problems

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