Parallel comparison algorithms for approximation problems

N. Alon, Y. Azar

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Suppose we have n elements from a totally ordered domain, and we are allowed to perform p parallel comparisons in each time unit (=round). In this paper we determine, up to a constant factor, the time complexity of several approximation problems in the common parallel comparison tree model of Valiant, for all admissible values of n, p and e{open}, where e{open} is an accuracy parameter determining the quality of the required approximation. The problems considered include the approximate maximum problem, approximate sorting and approximate merging. Our results imply as special cases, all the known results about the time complexity for parallel sorting, parallel merging and parallel selection of the maximum (in the comparison model), up to a constant factor. We mention one very special but representative result concerning the approximate maximum problem; suppose we wish to find, among the given n elements, one which belongs to the biggest n/2, where in each round we are allowed to ask n binary comparisons. We show that log*n+O(1) rounds are both necessary and sufficient in the best algorithm for this problem.

Original languageEnglish (US)
Pages (from-to)97-122
Number of pages26
Issue number2
StatePublished - Jun 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


  • AMS subject classification (1980): 68E05


Dive into the research topics of 'Parallel comparison algorithms for approximation problems'. Together they form a unique fingerprint.

Cite this