Abstract
We study comparator networks for selection, merging, and sorting that output the correct result with high probability given a random input permutation. We prove tight bounds, up to constant factors, on the size and depth of probabilistic (n, k)-selection networks. In the case of (n, n/2)-selection, our result gives a somewhat surprising bound of Θ(n log log n) on the size of networks of success probability in [δ, 1 - 1/poly(n)], where δ is an arbitrarily small positive constant, thus comparing favorably with the best previously known solutions, which have size Θ(n log n). We also prove tight bounds, up to lower order terms, on the size and depth of probabilistic merging networks of success probability in [δ, 1 - 1/poly(n)], where δ is an arbitrarily small positive constant. Finally, we describe two fairly simple probabilistic sorting networks of success probability at least 1 - 1/poly(n) and nearly logarithmic depth.
Original language | English (US) |
---|---|
Title of host publication | Annual ACM Symposium on Parallel Algorithms and Architectures |
Place of Publication | New York, NY, United States |
Publisher | ACM |
Pages | 106-118 |
Number of pages | 13 |
State | Published - 1995 |
Event | Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'95 - Santa Barbara, CA, USA Duration: Jul 17 1995 → Jul 19 1995 |
Other
Other | Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'95 |
---|---|
City | Santa Barbara, CA, USA |
Period | 7/17/95 → 7/19/95 |
ASJC Scopus subject areas
- Software
- Safety, Risk, Reliability and Quality