The asymptotic complexity of merging networks

Peter Bro Miltersen; Mike Paterson; Jun Tarui

doi:10.1145/227595.227693

The asymptotic complexity of merging networks

Peter Bro Miltersen, Mike Paterson, Jun Tarui

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

Abstract

Let M(m,n) be the minimum number of comparatorsneeded in a comparator network that merges m elements x1≤x2≤&cdots;≤xm and n elements y1≤y2≤&cdots;≤yn , where n≥m . Batcher's odd-even merge yields the following upper bound: Mm,n≤1 2m+nlog 2m+on; in particular, Mn,n≤nlog 2n+On. We prove the following lower bound that matches the upper bound above asymptotically as n≥m→∞: Mm,n≥1 2m+nlog 2m-Om; in particular, Mn,n≥nlog 2n-On. Our proof technique extends to give similarily tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.

Originalsprog	Engelsk
Tidsskrift	Association for Computing Machinery. Journal
Vol/bind	43
Nummer	1
Sider (fra-til)	147-165
ISSN	0004-5411
DOI	https://doi.org/10.1145/227595.227693
Status	Udgivet - 1996

Adgang til dokumentet

10.1145/227595.227693

Citationsformater

@article{9a5f09b0b1b911df8c1a000ea68e967b,

title = "The asymptotic complexity of merging networks",

abstract = "Let M(m,n) be the minimum number of comparatorsneeded in a comparator network that merges m elements x1≤x2≤&cdots;≤xm and n elements y1≤y2≤&cdots;≤yn , where n≥m . Batcher's odd-even merge yields the following upper bound: Mm,n≤1 2m+nlog 2m+on; in particular, Mn,n≤nlog 2n+On. We prove the following lower bound that matches the upper bound above asymptotically as n≥m→∞: Mm,n≥1 2m+nlog 2m-Om; in particular, Mn,n≥nlog 2n-On. Our proof technique extends to give similarily tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.",

author = "Miltersen, {Peter Bro} and Mike Paterson and Jun Tarui",

year = "1996",

doi = "10.1145/227595.227693",

language = "English",

volume = "43",

pages = "147--165",

journal = "Association for Computing Machinery. Journal",

issn = "0004-5411",

publisher = "Association for Computing Machinery",

number = "1",

}

TY - JOUR

T1 - The asymptotic complexity of merging networks

AU - Miltersen, Peter Bro

AU - Paterson, Mike

AU - Tarui, Jun

PY - 1996

Y1 - 1996

N2 - Let M(m,n) be the minimum number of comparatorsneeded in a comparator network that merges m elements x1≤x2≤&cdots;≤xm and n elements y1≤y2≤&cdots;≤yn , where n≥m . Batcher's odd-even merge yields the following upper bound: Mm,n≤1 2m+nlog 2m+on; in particular, Mn,n≤nlog 2n+On. We prove the following lower bound that matches the upper bound above asymptotically as n≥m→∞: Mm,n≥1 2m+nlog 2m-Om; in particular, Mn,n≥nlog 2n-On. Our proof technique extends to give similarily tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.

AB - Let M(m,n) be the minimum number of comparatorsneeded in a comparator network that merges m elements x1≤x2≤&cdots;≤xm and n elements y1≤y2≤&cdots;≤yn , where n≥m . Batcher's odd-even merge yields the following upper bound: Mm,n≤1 2m+nlog 2m+on; in particular, Mn,n≤nlog 2n+On. We prove the following lower bound that matches the upper bound above asymptotically as n≥m→∞: Mm,n≥1 2m+nlog 2m-Om; in particular, Mn,n≥nlog 2n-On. Our proof technique extends to give similarily tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.

U2 - 10.1145/227595.227693

DO - 10.1145/227595.227693

M3 - Journal article

SN - 0004-5411

VL - 43

SP - 147

EP - 165

JO - Association for Computing Machinery. Journal

JF - Association for Computing Machinery. Journal

IS - 1

ER -