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/