article

Free access

Lower Bounds on Merging Networks

Authors:

Andrew Chi-Chih Yao,

Foong Frances YaoAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 3

Pages 566 - 571

https://doi.org/10.1145/321958.321976

Published: 01 July 1976 Publication History

PDF eReader

Abstract

Let M(m, n) be the minimum number or comparators needed in an (m, n)-merging network. It is shown that M(m, n) ≥ n(lg(m + 1))/2, which implies that Batcher's merging networks are optimal up to a factor of 2 + ε for almost all values of m and n. The limit r_m = lim_n→∞ M(m, n)/n is determined to within 1. It is also proved that M(2, n) = [3n/2].

References

[1]

BATCHER, K E Sorting networks and their apphcatlons Proc AFIPS 1968 SJCC, Vol 32, AFIPS Press, Montvale, N J, pp 307-314

Google Scholar

[2]

FLOYD, R W Permuting reformation in ldeahzed two-level storage In Complexity of Computer Computations, R E Miller and J W Thatcher, Eds, Plenum Press, 1972, pp 105-110

Google Scholar

[3]

KNUTH, D E The Art of Computer Programming, Vol 1, 2nd ed Addison-Wesley, Reading, Mass, 1973

Crossref

Google Scholar

[4]

KNUTH, D E The Art of Computer Programming, Vol 3 Addison-Wesley, Reading, Mass, 1973

Crossref

Google Scholar

Cited By

View all

Bose PCano PFagerberg RIacono JJacob RLangerman S(2022)Fragile complexity of adaptive algorithmsTheoretical Computer Science10.1016/j.tcs.2022.03.034919:C(92-102)Online publication date: 5-Jun-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.03.034
Bose PCano PFagerberg RIacono JJacob RLangerman S(2021)Fragile Complexity of Adaptive AlgorithmsAlgorithms and Complexity10.1007/978-3-030-75242-2_10(144-157)Online publication date: 4-May-2021
https://doi.org/10.1007/978-3-030-75242-2_10
Brodal GPinotti M(2006)Comparator networks for binary heap constructionAlgorithm Theory — SWAT'9810.1007/BFb0054364(158-168)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0054364
Show More Cited By

Index Terms

Lower Bounds on Merging Networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Exponential Lower Bounds for AC⁰-Frege Imply Superpolynomial Frege Lower Bounds

We give a general transformation that turns polynomial-size Frege proofs into subexponential-size AC⁰-Frege proofs. This indicates that proving truly exponential lower bounds for AC⁰-Frege is hard, as it is a long-standing open problem to prove ...
Exponential lower bounds for AC⁰-Frege imply superpolynomial frege lower bounds
ICALP'11: Proceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I

We give a general transformation which turns polynomialsize Frege proofs to subexponential-size AC⁰-Frege proofs. This indicates that proving exponential lower bounds for AC⁰-Frege is hard, since it is a longstanding open problem to prove super-...
Lower Bounds for Merging Networks

A lower bound theorem is established for the number of comparators in a merging network. Let M(m, n) be the least number of comparators required in the (m, n)-merging networks, and let C(m, n) be the number of comparators in Batcher's (m, n)-merging ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 23, Issue 3

July 1976

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321958

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1976

Published in JACM Volume 23, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
638
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)6

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bose PCano PFagerberg RIacono JJacob RLangerman S(2022)Fragile complexity of adaptive algorithmsTheoretical Computer Science10.1016/j.tcs.2022.03.034919:C(92-102)Online publication date: 5-Jun-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.03.034
Bose PCano PFagerberg RIacono JJacob RLangerman S(2021)Fragile Complexity of Adaptive AlgorithmsAlgorithms and Complexity10.1007/978-3-030-75242-2_10(144-157)Online publication date: 4-May-2021
https://doi.org/10.1007/978-3-030-75242-2_10
Brodal GPinotti M(2006)Comparator networks for binary heap constructionAlgorithm Theory — SWAT'9810.1007/BFb0054364(158-168)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0054364
Hotz GStadel M(2005)Network complexityFundamentals of Computation Theory10.1007/3-540-08442-8_109(405-420)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08442-8_109
Morohashi GIwata S(2004)Some minimum merging networksTheoretical Computer Science10.1016/j.tcs.2004.09.003329:1-3(237-250)Online publication date: 13-Dec-2004
https://dl.acm.org/doi/10.1016/j.tcs.2004.09.003
Amano KMaruoka A(2003)On Optimal Merging NetworksMathematical Foundations of Computer Science 200310.1007/978-3-540-45138-9_9(152-161)Online publication date: 2003
https://doi.org/10.1007/978-3-540-45138-9_9
Brodal GPinotti M(2001)Comparator networks for binary heap constructionTheoretical Computer Science10.1016/S0304-3975(99)00137-1250:1-2(235-245)Online publication date: 6-Jan-2001
https://dl.acm.org/doi/10.1016/S0304-3975%2899%2900137-1
Iwata S(2001)Lower Bounds for Merging NetworksInformation and Computation10.1006/inco.2001.2934168:2(187-195)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.1006/inco.2001.2934
Leighton TMa YSuel T(1997)On Probabilistic Networks for Selection, Merging, and SortingTheory of Computing Systems10.1007/s00224000006830:6(559-582)Online publication date: 1-Dec-1997
https://dl.acm.org/doi/10.1007/s002240000068
Miltersen PPaterson MTarui J(1996)The asymptotic complexity of merging networksJournal of the ACM10.1145/227595.22769343:1(147-165)Online publication date: 1-Jan-1996
https://dl.acm.org/doi/10.1145/227595.227693
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds

Exponential lower bounds for AC0-Frege imply superpolynomial frege lower bounds

Lower Bounds for Merging Networks

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations

Exponential Lower Bounds for AC⁰-Frege Imply Superpolynomial Frege Lower Bounds

Exponential lower bounds for AC⁰-Frege imply superpolynomial frege lower bounds