Lower bounds for merging networks

DOI10.1006/INCO.2001.2934MaRDI QIDQ1854444zbMATH OpenOpenAlexFDO

Authors Shigeki Iwata

Publication date 14 January 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/68e314a5699005787aaf4a48afd21090866e395d

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Review text

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 network, respectively. We prove for \(n\geq 1\) that \(M(4,n)=C(4,n)\) for \(n\equiv 0,1,3\bmod 4, M(4,n)\geq C(4,n)-1\) for \(n\equiv 2\bmod 4\), and \(M(5,n)=C(5,n)\) for \(n\equiv 0,1,5\bmod 8\). Furthermore Batcher's \((6,8k+6)\)-, \((7,8k+7)\)-, and \((8,8k+8)\)-merging networks are optimal for \(k\geq 0\). Our lower bound for \((m,n)\)-merging networks, \(m\leq n\), has the same terms as \(C(m,n)\) has as far as \(n\) is concerned. Thus Batcher's \((m,n)\)-merging network is optimal up to a constant number of comparators, where the constant depends only on \(m\). An open problem posed by \textit{A. C.-C. Yao} and \textit{F. F. Yao} [J. Assoc. Comput. Mach. 23, 566-571 (1976; Zbl 0335.68034)] is solved: \(\lim_{n\to\infty}M(m,n)/n=\lceil\log m\rceil/2+m/2^{\lceil\log m\rceil}\).

Recommendations

• Bounds on the size of merging networks
• The asymptotic complexity of merging networks
• scientific article; zbMATH DE number 1256659
• Some minimum merging networks
• Mathematical Foundations of Computer Science 2003
• scientific article; zbMATH DE number 1263220
• Lower bounds on communication overlap of networks
• On the asymptotic merging of the set of nodes in stochastic networks
• Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults
• Toward a lower bound for sorting networks

Cites work

• Bounds on the size of merging networks
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Lower Bounds on Merging Networks
• The asymptotic complexity of merging networks

Cited in

(9)

• Reaching the bound in the \((2,n)\) merging problem
• Bounds on the size of merging networks
• scientific article; zbMATH DE number 17819 (Why is no real title available?)
• scientific article; zbMATH DE number 1256659 (Why is no real title available?)
• The asymptotic complexity of merging networks
• Optimal Conclusive Sets for Comparator Networks
• Mathematical Foundations of Computer Science 2003
• Some minimum merging networks
• Area complexity of merging

This page was built for publication: Lower bounds for merging networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854444)