Optimal parallel weighted multiselection

Weighted multiselection requires to select r elements from a given set of a elements, each associated with a weight such that each element selected is on a pre-specifed weighted-rank, where an element is on weighted-rank k if it is the smallest element such that the aggregated weight of all elements not greater than it in the set is not smaller than k. This paper presents efficient algorithms for solving this problem both sequentially and in parallel on EREW PRAM. Our sequential algorithm solves this problem in time O(n log r) which is optimal. Our parallel algorithm runs in O(T-1 log r) time on an EREW PRAM with 1 < p less than or equal to n processors, and is optimal with respect to T-1 which is the time complexity for single-element weighted selection using p processors.We give a parallel algorithm for single-element weighted selection using p EREW processors which runs cost-optimally in O(n/p) time for 1 < p less than or equal to n log log n/log n,' and time-optimally in O(log n/log log n) time for n log log n/log n < p < n.