TY - GEN

T1 - Parallel comparison algorithms for approximation problems

AU - Alon, N.

AU - Azar, Y.

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1988

Y1 - 1988

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0024143266&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024143266&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1988.21937

DO - 10.1109/sfcs.1988.21937

M3 - Conference contribution

AN - SCOPUS:0024143266

SN - 0818608773

SN - 9780818608773

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 194

EP - 203

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

ER -