Parallel comparison algorithms for approximation problems

N. Alon, Y. Azar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


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

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Number of pages10
ISBN (Print)0818608773, 9780818608773
StatePublished - 1988
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture


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

Cite this