Geodesic
A~random algorithm for multiselection
Diskretnaya Matematika, Tome 18 (2006) no. 3, pp. 95-101.

Voir la notice de l'article provenant de la source Math-Net.Ru

Given a set $S$ of $n$ elements drawn from a linearly ordered set and a set $K=\{k_1,k_2,\ldots,k_r\}$ of positive integers between 1 and $n$, the multiselection problem is to select the $k_i$th smallest element for all values of $i$, $1\le i\le r$. We present an efficient randomised algorithm to solve this problem in time $O(n\ln r)$ with probability at least $1-cn^{-1}$, where $c$ is a positive constant. 
@article{DM_2006_18_3_a6,
     author = {M. H. Alsuwaiyel},
     title = {A~random algorithm for multiselection},
     journal = {Diskretnaya Matematika},
     pages = {95--101},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_3_a6/}
}
TY  - JOUR
AU  - M. H. Alsuwaiyel
TI  - A~random algorithm for multiselection
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 95
EP  - 101
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_3_a6/
LA  - ru
ID  - DM_2006_18_3_a6
ER  - 
%0 Journal Article
%A M. H. Alsuwaiyel
%T A~random algorithm for multiselection
%J Diskretnaya Matematika
%D 2006
%P 95-101
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2006_18_3_a6/
%G ru
%F DM_2006_18_3_a6
M. H. Alsuwaiyel. A~random algorithm for multiselection. Diskretnaya Matematika, Tome 18 (2006) no. 3, pp. 95-101. http://geodesic.mathdoc.fr/item/DM_2006_18_3_a6/

[1] Akl S. G., The design and analysis of parallet algorithms, Prentice Hall, Englewood Cliffs, 1989 | Zbl

[2] Alsuwaiyel M. H., “An optimal parallel algorithm for the multiselection problem”, Parallel Computing, 27:6 (2001), 861–865 | DOI | MR | Zbl

[3] Alsuwaiyel M. H., “An efficient and adaptive algorithm for multiselection on the PRAM”, Proc. ACIS 2nd Intern. Conf. Software Engineering, Artificial Intelligence, Networking and Parallel Computing (Japan, 2001), 140–143

[4] Blum M., Floyd R. W., Pratt V. R., Rivest R. L., Tarjan R. E., “Time bounds for selection”, J. Computer System Sci., 7 (1973), 448–461 | DOI | MR | Zbl

[5] Floyd R. W., Rivest R. L., “Expected time bounds for selection”, Commun. ACM, 18 (1975), 165–172 | DOI | Zbl

[6] Fredman M. L., Spencer T. H., “Refined complexity analysis for heap operations”, J. Computer System Sci., 21 (1987), 269–284 | DOI | MR

[7] Hoare C. A. R., “FIND (Algorithm 65)”, Commun. ACM, 4 (1961), 321–322 | DOI

[8] Motwani R., Rajhavan P., Randomized Algorithms, Cambridge Univ. Press, Cambridge, 1995 | MR | Zbl

[9] Shen H., “Optimal parallel multiselection on EREW PRAM”, Parallel Computing, 23 (1997), 1987–1992 | DOI | MR | Zbl

[10] Shen H., “Efficient parallel multiselection on hypercubes”, Proc. 1997 Intern. Symp. on Parallel Architectures, Algorithms and Networks, IEEE CS Press, 1997, 338–342

[11] Shen H., “Optimal multiselection in hypercubes”, Parallel Algorithms Appl., 14 (2000), 203–212 | MR | Zbl

[12] Shen H., Han Y., Pan Y., Evans D. J., “Optimal parallel algorithms for multiselection on mesh-connected computers”, Intern. J. Comput. Math., 80 (2003), 165–179 | DOI | MR | Zbl

[13] Shen H., Chin F., “Selection and multiselection on multidimensional meshes”, Proc. Intern. Conf. on Parallel and Distributed Processing Techn. and Appl., 2002, 899–906