Fast generation of random permutations via networks simulation
Identifieur interne : 001741 ( Istex/Corpus ); précédent : 001740; suivant : 001742Fast generation of random permutations via networks simulation
Auteurs : Artur Czumaj ; Przemysława Kanarek ; Mirosław Kutyłowski ; Krzysztof LorySource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1996.
Abstract
Abstract: We consider the classical problem of generating random permutations with the uniform distribution. That is, we require that for an arbitrary permutation π of n elements, with probability 1/n! the machine halts with the ith output cell containing π(i), for 1≤i≤n. We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM. The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n 1+o(1)) processors on the CREW PRAM. This is the first o(log n)-time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm matches the running time and the number of processors used of the best previously known algorithms for the CREW PRAM, and performs better as far as the memory usage is considered. The common and novel feature of both our algorithms is to design first a suitable random network generating a permutation and then to simulate this network on the PRAM model in a fast way.
Url:
DOI: 10.1007/3-540-61680-2_60
Links to Exploration step
ISTEX:B7EF9ACF75434C20F1E67028E2C985AC22552AF9Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Fast generation of random permutations via networks simulation</title><author><name sortKey="Czumaj, Artur" sort="Czumaj, Artur" uniqKey="Czumaj A" first="Artur" last="Czumaj">Artur Czumaj</name><affiliation><mods:affiliation>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: artur@uni-paderborn.de</mods:affiliation></affiliation></author><author><name sortKey="Kanarek, Przemyslawa" sort="Kanarek, Przemyslawa" uniqKey="Kanarek P" first="Przemysława" last="Kanarek">Przemysława Kanarek</name><affiliation><mods:affiliation>Institute of Computer Science, University of Wrocław, Przesmyckiego 20, PL-51-151, Wrocław, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: pka@tcs.uni.wroc.pl</mods:affiliation></affiliation></author><author><name sortKey="Kutylowski, Miroslaw" sort="Kutylowski, Miroslaw" uniqKey="Kutylowski M" first="Mirosław" last="Kutyłowski">Mirosław Kutyłowski</name><affiliation><mods:affiliation>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: mirekk@uni-paderborn.de</mods:affiliation></affiliation></author><author><name sortKey="Lory, Krzysztof" sort="Lory, Krzysztof" uniqKey="Lory K" first="Krzysztof" last="Lory">Krzysztof Lory</name><affiliation><mods:affiliation>Institute of Computer Science, University of Wrocław, Przesmyckiego 20, PL-51-151, Wrocław, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>Department of Computer Science, University of Trier, D-54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: lorys@tcs.uni.wroc.pl</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:B7EF9ACF75434C20F1E67028E2C985AC22552AF9</idno><date when="1996" year="1996">1996</date><idno type="doi">10.1007/3-540-61680-2_60</idno><idno type="url">https://api.istex.fr/document/B7EF9ACF75434C20F1E67028E2C985AC22552AF9/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001741</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001741</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Fast generation of random permutations via networks simulation</title><author><name sortKey="Czumaj, Artur" sort="Czumaj, Artur" uniqKey="Czumaj A" first="Artur" last="Czumaj">Artur Czumaj</name><affiliation><mods:affiliation>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: artur@uni-paderborn.de</mods:affiliation></affiliation></author><author><name sortKey="Kanarek, Przemyslawa" sort="Kanarek, Przemyslawa" uniqKey="Kanarek P" first="Przemysława" last="Kanarek">Przemysława Kanarek</name><affiliation><mods:affiliation>Institute of Computer Science, University of Wrocław, Przesmyckiego 20, PL-51-151, Wrocław, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: pka@tcs.uni.wroc.pl</mods:affiliation></affiliation></author><author><name sortKey="Kutylowski, Miroslaw" sort="Kutylowski, Miroslaw" uniqKey="Kutylowski M" first="Mirosław" last="Kutyłowski">Mirosław Kutyłowski</name><affiliation><mods:affiliation>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: mirekk@uni-paderborn.de</mods:affiliation></affiliation></author><author><name sortKey="Lory, Krzysztof" sort="Lory, Krzysztof" uniqKey="Lory K" first="Krzysztof" last="Lory">Krzysztof Lory</name><affiliation><mods:affiliation>Institute of Computer Science, University of Wrocław, Przesmyckiego 20, PL-51-151, Wrocław, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>Department of Computer Science, University of Trier, D-54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: lorys@tcs.uni.wroc.pl</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1996</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">B7EF9ACF75434C20F1E67028E2C985AC22552AF9</idno><idno type="DOI">10.1007/3-540-61680-2_60</idno><idno type="ChapterID">19</idno><idno type="ChapterID">Chap19</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We consider the classical problem of generating random permutations with the uniform distribution. That is, we require that for an arbitrary permutation π of n elements, with probability 1/n! the machine halts with the ith output cell containing π(i), for 1≤i≤n. We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM. The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n 1+o(1)) processors on the CREW PRAM. This is the first o(log n)-time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm matches the running time and the number of processors used of the best previously known algorithms for the CREW PRAM, and performs better as far as the memory usage is considered. The common and novel feature of both our algorithms is to design first a suitable random network generating a permutation and then to simulate this network on the PRAM model in a fast way.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Artur Czumaj</name><affiliations><json:string>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</json:string><json:string>E-mail: artur@uni-paderborn.de</json:string></affiliations></json:item><json:item><name>Przemysława Kanarek</name><affiliations><json:string>Institute of Computer Science, University of Wrocław, Przesmyckiego 20, PL-51-151, Wrocław, Poland</json:string><json:string>E-mail: pka@tcs.uni.wroc.pl</json:string></affiliations></json:item><json:item><name>Mirosław Kutyłowski</name><affiliations><json:string>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</json:string><json:string>E-mail: mirekk@uni-paderborn.de</json:string></affiliations></json:item><json:item><name>Krzysztof Loryś</name><affiliations><json:string>Institute of Computer Science, University of Wrocław, Przesmyckiego 20, PL-51-151, Wrocław, Poland</json:string><json:string>Department of Computer Science, University of Trier, D-54286, Trier, Germany</json:string><json:string>E-mail: lorys@tcs.uni.wroc.pl</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>ReviewPaper</json:string></originalGenre><abstract>Abstract: We consider the classical problem of generating random permutations with the uniform distribution. That is, we require that for an arbitrary permutation π of n elements, with probability 1/n! the machine halts with the ith output cell containing π(i), for 1≤i≤n. We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM. The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n 1+o(1)) processors on the CREW PRAM. This is the first o(log n)-time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm matches the running time and the number of processors used of the best previously known algorithms for the CREW PRAM, and performs better as far as the memory usage is considered. The common and novel feature of both our algorithms is to design first a suitable random network generating a permutation and then to simulate this network on the PRAM model in a fast way.</abstract><qualityIndicators><score>7.292</score><pdfVersion>1.3</pdfVersion><pdfPageSize>439.28 x 666 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>1117</abstractCharCount><pdfWordCount>6226</pdfWordCount><pdfCharCount>29493</pdfCharCount><pdfPageCount>15</pdfPageCount><abstractWordCount>191</abstractWordCount></qualityIndicators><title>Fast generation of random permutations via networks simulation</title><chapterId><json:string>19</json:string><json:string>Chap19</json:string></chapterId><refBibs><json:item><author><json:item><name>R Anderson</name></json:item></author><host><pages><last>102</last><first>95</first></pages><author></author><title>Proc. ~nd Annual ACM Symposium on Parallel Algorithms and Architectures</title><publicationDate>1990</publicationDate></host><title>Parallel algorithms for generating random permutations on a shared memory ma~.hine</title><publicationDate>1990</publicationDate></json:item><json:item><author><json:item><name>A Borodin</name></json:item><json:item><name>J,E Hopcroft</name></json:item></author><host><volume>30</volume><pages><last>145</last><first>130</first></pages><author></author><title>J. Comput. System Sci</title><publicationDate>1985</publicationDate></host><title>Routing, merging, and sorting on parallel models of computktion</title><publicationDate>1985</publicationDate></json:item><json:item><author><json:item><name>1~ Cole</name></json:item></author><host><volume>17</volume><pages><last>785</last><first>770</first></pages><author></author><title>SIAM J. Comput</title><publicationDate>1988</publicationDate></host><title>Parallel merge sort</title><publicationDate>1988</publicationDate></json:item><json:item><author><json:item><name>S Cook</name></json:item><json:item><name>C Dwork</name></json:item><json:item><name>R Reischuk</name></json:item></author><host><volume>15</volume><pages><last>97</last><first>87</first></pages><author></author><title>SIAM J. Comput</title><publicationDate>1986</publicationDate></host><title>Upper and lower bounds for parallel random access machines without simultaneous writes</title><publicationDate>1986</publicationDate></json:item><json:item><author><json:item><name>M Dietzfelbinger</name></json:item><json:item><name>M Kutytowski</name></json:item><json:item><name>R Reischuk</name></json:item></author><host><volume>48</volume><pages><last>254</last><first>231</first></pages><author></author><title>J. Comput. System Sci</title><publicationDate>1994</publicationDate></host><title>Exact lower time bounds for computing boolean functions on CREW PRAMs</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>R Durstenfeld</name></json:item></author><host><volume>7</volume><pages><first>420</first></pages><author></author><title>Comm. ACM</title><publicationDate>1964</publicationDate></host><title>Random permutation (Algorithm 235)</title><publicationDate>1964</publicationDate></json:item><json:item><author><json:item><name>A Gottlieb</name></json:item><json:item><name>C,P </name></json:item></author><host><volume>31</volume><pages><last>209</last><first>193</first></pages><author></author><title>J. Assoc. Comput. Math</title><publicationDate>1984</publicationDate></host><title>Complexity results for permuting data and other computations on parallel processors</title><publicationDate>1984</publicationDate></json:item><json:item><author><json:item><name>T Hagerup</name></json:item></author><host><pages><last>416</last><first>405</first></pages><author></author><title>Proc. 18th Annual International Colloquium on Automata, Languages and Programming, ICALP'91</title><publicationDate>1991</publicationDate></host><title>Fast parallel generation of random permutations</title><publicationDate>1991</publicationDate></json:item><json:item><host><author><json:item><name>D,E Knuth</name></json:item></author><title>The Art of Computer Programming: Seminumerical Algorithms</title><publicationDate>1981</publicationDate></host></json:item><json:item><author><json:item><name>Y Matias</name></json:item><json:item><name>U Vishkin</name></json:item></author><host><pages><last>316</last><first>307</first></pages><author></author><title>Proc. 23rd Annual ACM Symposium on Theory of Computing</title><publicationDate>1991</publicationDate></host><title>Converting high probability into nearly-constant time -with applications to parallel hashing</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>G,L Miller</name></json:item><json:item><name>J,H Reff</name></json:item></author><host><pages><last>489</last><first>478</first></pages><author></author><title>Computer Science</title><publicationDate>1985</publicationDate></host><title>Parallel tree contraction, in ]~ 26 Symposium on Foundations of</title><publicationDate>1985</publicationDate></json:item><json:item><author><json:item><name>G,L Miller</name></json:item><json:item><name>J,H Reif</name></json:item></author><host><volume>5</volume><pages><last>72</last><first>47</first></pages><author></author><title>Adv. in Comput. Res</title><publicationDate>1989</publicationDate></host><title>Parallel tree contraction</title><publicationDate>1989</publicationDate></json:item><json:item><host><author><json:item><name>R Motwani</name></json:item><json:item><name>P Raghavan</name></json:item></author><title>Randomized Algorithms</title><publicationDate>1995</publicationDate></host></json:item><json:item><host><author><json:item><name>K Mulmuley</name></json:item><json:item><name>Computational Geometry</name></json:item></author><title>An Introduction Through Randomized Algorithms</title><publicationDate>1994</publicationDate></host></json:item><json:item><author><json:item><name>S Rajasekaran</name></json:item><json:item><name>J Reif</name></json:item></author><host><volume>19</volume><pages><last>607</last><first>594</first></pages><author></author><title>SIAM J. Comput</title><publicationDate>1989</publicationDate></host><title>Optimal and sublogarithmic'time randomized parallel sorting algorithms</title><publicationDate>1989</publicationDate></json:item><json:item><author><json:item><name>J Reif</name></json:item></author><host><pages><last>5</last><first>490</first></pages><author></author><title>Proc. 26 Symposium on Foundations of Computer Science</title><publicationDate>1985</publicationDate></host><title>An optimal parallel algorithm for integer sorting</title><publicationDate>1985</publicationDate></json:item><json:item><author><json:item><name>1~ Sedgewick</name></json:item></author><host><volume>9</volume><pages><last>164</last><first>138</first></pages><author></author><title>ACM Comput. Surv</title><publicationDate>1977</publicationDate></host><title>Permutation generation methods</title><publicationDate>1977</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name></json:item><json:item><name>Juris Hartmanis</name></json:item><json:item><name>Jan van Leeuwen</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>1996</copyrightDate></serie><host><editor><json:item><name>Josep Diaz</name></json:item><json:item><name>Maria Serna</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Combinatorics</value></json:item><json:item><value>Computer Graphics</value></json:item><json:item><value>Data Structures</value></json:item><json:item><value>Computer Communication Networks</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item></subject><isbn><json:string>978-3-540-61680-1</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Algorithms — ESA '96</title><bookId><json:string>3540616802</json:string></bookId><volume>1136</volume><pages><last>260</last><first>246</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-70667-0</json:string></eisbn><copyrightDate>1996</copyrightDate><doi><json:string>10.1007/3-540-61680-2</json:string></doi></host><publicationDate>2005</publicationDate><copyrightDate>1996</copyrightDate><doi><json:string>10.1007/3-540-61680-2_60</json:string></doi><id>B7EF9ACF75434C20F1E67028E2C985AC22552AF9</id><score>0.5143218</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/B7EF9ACF75434C20F1E67028E2C985AC22552AF9/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/B7EF9ACF75434C20F1E67028E2C985AC22552AF9/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/B7EF9ACF75434C20F1E67028E2C985AC22552AF9/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Fast generation of random permutations via networks simulation</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag, 1996</p></availability><date>1996</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Fast generation of random permutations via networks simulation</title><author xml:id="author-1"><persName><forename type="first">Artur</forename><surname>Czumaj</surname></persName><email>artur@uni-paderborn.de</email><affiliation>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">Przemysława</forename><surname>Kanarek</surname></persName><email>pka@tcs.uni.wroc.pl</email><affiliation>Institute of Computer Science, University of Wrocław, Przesmyckiego 20, PL-51-151, Wrocław, Poland</affiliation></author><author xml:id="author-3"><persName><forename type="first">Mirosław</forename><surname>Kutyłowski</surname></persName><email>mirekk@uni-paderborn.de</email><affiliation>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</affiliation></author><author xml:id="author-4"><persName><forename type="first">Krzysztof</forename><surname>Loryś</surname></persName><email>lorys@tcs.uni.wroc.pl</email><affiliation>Institute of Computer Science, University of Wrocław, Przesmyckiego 20, PL-51-151, Wrocław, Poland</affiliation><affiliation>Department of Computer Science, University of Trier, D-54286, Trier, Germany</affiliation></author></analytic><monogr><title level="m">Algorithms — ESA '96</title><title level="m" type="sub">Fourth Annual European Symposium Barcelona, Spain, September 25–27, 1996 Proceedings</title><idno type="pISBN">978-3-540-61680-1</idno><idno type="eISBN">978-3-540-70667-0</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/3-540-61680-2</idno><idno type="book-ID">3540616802</idno><idno type="book-title-ID">45054</idno><idno type="book-volume-number">1136</idno><idno type="book-chapter-count">41</idno><editor><persName><forename type="first">Josep</forename><surname>Diaz</surname></persName></editor><editor><persName><forename type="first">Maria</forename><surname>Serna</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2005-06-06"></date><biblScope unit="volume">1136</biblScope><biblScope unit="page" from="246">246</biblScope><biblScope unit="page" to="260">260</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName></editor><biblScope><date>1996</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">B7EF9ACF75434C20F1E67028E2C985AC22552AF9</idno><idno type="DOI">10.1007/3-540-61680-2_60</idno><idno type="ChapterID">19</idno><idno type="ChapterID">Chap19</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1996</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: We consider the classical problem of generating random permutations with the uniform distribution. That is, we require that for an arbitrary permutation π of n elements, with probability 1/n! the machine halts with the ith output cell containing π(i), for 1≤i≤n. We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM. The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n 1+o(1)) processors on the CREW PRAM. This is the first o(log n)-time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm matches the running time and the number of processors used of the best previously known algorithms for the CREW PRAM, and performs better as far as the memory usage is considered. The common and novel feature of both our algorithms is to design first a suitable random network generating a permutation and then to simulate this network on the PRAM model in a fast way.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16021</label><label>M17009</label><label>I22013</label><label>I15017</label><label>I13022</label><label>I17028</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Combinatorics</term></item><item><term>Computer Graphics</term></item><item><term>Data Structures</term></item><item><term>Computer Communication Networks</term></item><item><term>Discrete Mathematics in Computer Science</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2005-06-06">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-23">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-21">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/B7EF9ACF75434C20F1E67028E2C985AC22552AF9/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle><SeriesAbbreviatedTitle>Lect Notes Comput Sci</SeriesAbbreviatedTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3540616802</BookID><BookTitle>Algorithms — ESA '96</BookTitle><BookSubTitle>Fourth Annual European Symposium Barcelona, Spain, September 25–27, 1996 Proceedings</BookSubTitle><BookVolumeNumber>1136</BookVolumeNumber><BookDOI>10.1007/3-540-61680-2</BookDOI><BookTitleID>45054</BookTitleID><BookPrintISBN>978-3-540-61680-1</BookPrintISBN><BookElectronicISBN>978-3-540-70667-0</BookElectronicISBN><BookChapterCount>41</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1996</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="M17009" Priority="2" Type="Secondary">Combinatorics</BookSubject><BookSubject Code="I22013" Priority="3" Type="Secondary">Computer Graphics</BookSubject><BookSubject Code="I15017" Priority="4" Type="Secondary">Data Structures</BookSubject><BookSubject Code="I13022" Priority="5" Type="Secondary">Computer Communication Networks</BookSubject><BookSubject Code="I17028" Priority="6" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Josep</GivenName><FamilyName>Diaz</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Maria</GivenName><FamilyName>Serna</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap19" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>19</ChapterID><ChapterDOI>10.1007/3-540-61680-2_60</ChapterDOI><ChapterSequenceNumber>19</ChapterSequenceNumber><ChapterTitle Language="En">Fast generation of random permutations via networks simulation</ChapterTitle><ChapterFirstPage>246</ChapterFirstPage><ChapterLastPage>260</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1996</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>6</Month><Day>6</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3540616802</BookID><BookTitle>Algorithms — ESA '96</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Artur</GivenName><FamilyName>Czumaj</FamilyName></AuthorName><Contact><Email>artur@uni-paderborn.de</Email></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Przemysława</GivenName><FamilyName>Kanarek</FamilyName></AuthorName><Contact><Email>pka@tcs.uni.wroc.pl</Email></Contact></Author><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Mirosław</GivenName><FamilyName>Kutyłowski</FamilyName></AuthorName><Contact><Email>mirekk@uni-paderborn.de</Email></Contact></Author><Author AffiliationIDS="Aff2 Aff3"><AuthorName DisplayOrder="Western"><GivenName>Krzysztof</GivenName><FamilyName>Loryś</FamilyName></AuthorName><Contact><Email>lorys@tcs.uni.wroc.pl</Email></Contact></Author><Affiliation ID="Aff1"><OrgDivision>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science</OrgDivision><OrgName>University of Paderborn</OrgName><OrgAddress><Postcode>D-33095</Postcode><City>Paderborn</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Institute of Computer Science</OrgDivision><OrgName>University of Wrocław</OrgName><OrgAddress><Street>Przesmyckiego 20</Street><Postcode>PL-51-151</Postcode><City>Wrocław</City><Country>Poland</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgDivision>Department of Computer Science</OrgDivision><OrgName>University of Trier</OrgName><OrgAddress><Postcode>D-54286</Postcode><City>Trier</City><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>We consider the classical problem of generating random permutations with the uniform distribution. That is, we require that for an arbitrary permutation <Emphasis Type="Italic">π</Emphasis> of <Emphasis Type="Italic">n</Emphasis> elements, with probability 1/n! the machine halts with the <Emphasis Type="Italic">i</Emphasis>th output cell containing <Emphasis Type="Italic">π(i)</Emphasis>, for 1≤<Emphasis Type="Italic">i</Emphasis>≤<Emphasis Type="Italic">n</Emphasis>. We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM.</Para><Para>The main result of the paper is an algorithm for generating random permutations that runs in <Emphasis Type="Italic">O</Emphasis>(log log <Emphasis Type="Italic">n</Emphasis>) time and uses <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>1+<Emphasis Type="Italic">o</Emphasis>(1)</Superscript>) processors on the CREW PRAM. This is the first <Emphasis Type="Italic">o</Emphasis>(log <Emphasis Type="Italic">n</Emphasis>)-time CREW PRAM algorithm for this problem.</Para><Para>On the EREW PRAM we present a simple algorithm that generates a random permutation in time <Emphasis Type="Italic">O</Emphasis>(log <Emphasis Type="Italic">n</Emphasis>) using <Emphasis Type="Italic">n</Emphasis> processors and <Emphasis Type="Italic">O(n)</Emphasis> space. This algorithm matches the running time and the number of processors used of the best previously known algorithms for the CREW PRAM, and performs better as far as the memory usage is considered.</Para><Para>The common and novel feature of both our algorithms is to design first a suitable random network generating a permutation and then to simulate this network on the PRAM model in a fast way.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>Partially supported by KBN grant 8 S503 002 07, TEMPUS project JEP 8145, EU ESPRIT Long Term Research Project 20244 (ALCOM-IT), DFG-Sonderforschungsbereich 376 “Massive Parallelität” and DFG Leibniz Grant Me872/6-1.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Fast generation of random permutations via networks simulation</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Fast generation of random permutations via networks simulation</title></titleInfo><name type="personal"><namePart type="given">Artur</namePart><namePart type="family">Czumaj</namePart><affiliation>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</affiliation><affiliation>E-mail: artur@uni-paderborn.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Przemysława</namePart><namePart type="family">Kanarek</namePart><affiliation>Institute of Computer Science, University of Wrocław, Przesmyckiego 20, PL-51-151, Wrocław, Poland</affiliation><affiliation>E-mail: pka@tcs.uni.wroc.pl</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Mirosław</namePart><namePart type="family">Kutyłowski</namePart><affiliation>Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</affiliation><affiliation>E-mail: mirekk@uni-paderborn.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Krzysztof</namePart><namePart type="family">Loryś</namePart><affiliation>Institute of Computer Science, University of Wrocław, Przesmyckiego 20, PL-51-151, Wrocław, Poland</affiliation><affiliation>Department of Computer Science, University of Trier, D-54286, Trier, Germany</affiliation><affiliation>E-mail: lorys@tcs.uni.wroc.pl</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="ReviewPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2005-06-06</dateIssued><copyrightDate encoding="w3cdtf">1996</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: We consider the classical problem of generating random permutations with the uniform distribution. That is, we require that for an arbitrary permutation π of n elements, with probability 1/n! the machine halts with the ith output cell containing π(i), for 1≤i≤n. We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM. The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n 1+o(1)) processors on the CREW PRAM. This is the first o(log n)-time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm matches the running time and the number of processors used of the best previously known algorithms for the CREW PRAM, and performs better as far as the memory usage is considered. The common and novel feature of both our algorithms is to design first a suitable random network generating a permutation and then to simulate this network on the PRAM model in a fast way.</abstract><relatedItem type="host"><titleInfo><title>Algorithms — ESA '96</title><subTitle>Fourth Annual European Symposium Barcelona, Spain, September 25–27, 1996 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Josep</namePart><namePart type="family">Diaz</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Maria</namePart><namePart type="family">Serna</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">1996</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="M17009">Combinatorics</topic><topic authority="SpringerSubjectCodes" authorityURI="I22013">Computer Graphics</topic><topic authority="SpringerSubjectCodes" authorityURI="I15017">Data Structures</topic><topic authority="SpringerSubjectCodes" authorityURI="I13022">Computer Communication Networks</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic></subject><identifier type="DOI">10.1007/3-540-61680-2</identifier><identifier type="ISBN">978-3-540-61680-1</identifier><identifier type="eISBN">978-3-540-70667-0</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">45054</identifier><identifier type="BookID">3540616802</identifier><identifier type="BookChapterCount">41</identifier><identifier type="BookVolumeNumber">1136</identifier><part><date>1996</date><detail type="volume"><number>1136</number><caption>vol.</caption></detail><extent unit="pages"><start>246</start><end>260</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">1996</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></relatedItem><identifier type="istex">B7EF9ACF75434C20F1E67028E2C985AC22552AF9</identifier><identifier type="DOI">10.1007/3-540-61680-2_60</identifier><identifier type="ChapterID">19</identifier><identifier type="ChapterID">Chap19</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag, 1996</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001741 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001741 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:B7EF9ACF75434C20F1E67028E2C985AC22552AF9
|texte= Fast generation of random permutations via networks simulation
}}
| This area was generated with Dilib version V0.6.31. |  |