On Probabilistic Networks for Selection, Merging, and Sorting |
| |
Authors: | T Leighton Y Ma T Suel |
| |
Affiliation: | (1) Department of Mathematics and Laboratory for Computer Science, MIT, Cambridge, MA 02139, USA ftl@math.mit.edu , US;(2) Haas School of Business, University of California, Berkeley, CA 94720, USA yuan@haas.berkeley.edu , US;(3) Bell Laboratories, 700 Mountain Avenue, Murray Hill, NJ 07974, USA suel@bell-labs.com, US |
| |
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 on the size of networks of success probability in , where δ is an arbitrarily small positive constant, thus comparing favorably with the best previously known solutions, which have
size . We also prove tight bounds, up to lower-order terms, on the size and depth of probabilistic merging networks of success
probability in , where δ is an arbitrarily small positive constant. Finally, we describe two fairly simple probabilistic sorting networks of success
probability at least and nearly logarithmic depth.
Received January 22, 1996, and in final form February 14, 1997. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|