On probabilistic networks for selection, merging, and sorting

Tom Leighton, Yuan Ma, Torsten Suel

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

    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 languageEnglish (US)
    Title of host publicationAnnual ACM Symposium on Parallel Algorithms and Architectures
    Place of PublicationNew York, NY, United States
    PublisherACM
    Pages106-118
    Number of pages13
    StatePublished - 1995
    EventProceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'95 - Santa Barbara, CA, USA
    Duration: Jul 17 1995Jul 19 1995

    Other

    OtherProceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'95
    CitySanta Barbara, CA, USA
    Period7/17/957/19/95

    ASJC Scopus subject areas

    • Software
    • Safety, Risk, Reliability and Quality

    Fingerprint Dive into the research topics of 'On probabilistic networks for selection, merging, and sorting'. Together they form a unique fingerprint.

  • Cite this

    Leighton, T., Ma, Y., & Suel, T. (1995). On probabilistic networks for selection, merging, and sorting. In Annual ACM Symposium on Parallel Algorithms and Architectures (pp. 106-118). ACM.