Name
Title | ||
|---|---|---|
Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model |
Abstract | ||
|---|---|---|
The limit laws of three cost measures are derived of two algorithms for finding the maximum in a single-channel broadcast communication model. Both algorithms use coin flips and comparisons. Besides the ubiquitous normal limit law, the Dickman distribution also appears in a natural way. The method of proof proceeds along the line via the method of moments and the "asymptotic transfers," which roughly bridges the asymptotics of the "conquering cost of the subproblems" and that of the total cost. Such a general approach has proved very fruitful for a number of problems in the analysis of recursive algorithms. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0196-6774(02)00293-6 | J. Algorithms |
Keywords | DocType | Volume |
randomized algorithm,broadcast communication model,total cost,dickman distribution,conquering cost,ubiquitous normal limit law,asymptotic transfer,general approach,algorithms use coin,limit law,proof proceed,cost measure,communication model,limit laws,recursive algorithm,asymptotic normality | Journal | 46 |
Issue | ISSN | Citations |
2 | 0196-6774 | 3 |
PageRank | References | Authors |
0.40 | 20 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wei‐Mei Chen | 1 | 57 | 9.26 |
| Hsien-Kuei Hwang | 2 | 365 | 38.02 |