### Abstract

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 language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | Publ by IEEE |

Pages | 194-203 |

Number of pages | 10 |

ISBN (Print) | 0818608773, 9780818608773 |

DOIs | |

State | Published - 1988 |

Externally published | Yes |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### All Science Journal Classification (ASJC) codes

- Hardware and Architecture

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

## Cite this

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 194-203). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1988.21937