@inproceedings{f99d7c71cb704cebb345df4d4b35b71c,

title = "Efficient weighted multiselection in parallel architectures",

abstract = "We study parallel solutions to the problem of weighted multiselection to select r elements on given weighted-ranks from a set S of n weighted elements, 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 S is not smaller than k. We propose efficient algorithms on two of the most popular parallel architectures, hypercube and mesh. For a hypercube with p < n processors, we present a parallel algorithm running in 0(n∈ min{r, log p}) time for p = n1-∈, 0 < ∈ < 1, which is cost optimal when r ≥ p. Our algorithm on √p x √p- mesh runs in O(√p + p-n log3 p) time which is the same as multiselection on mesh when r ≥ logp, and thus has the same optimality as multiselection in this case.",

keywords = "Hypercube, mesh, multiselection, parallel algorithm, weighted selection",

author = "Hong Shen",

note = "Publisher Copyright: {\textcopyright} 2002 IEEE.; 5th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2002 ; Conference date: 23-10-2002 Through 25-10-2002",

year = "2002",

doi = "10.1109/ICAPP.2002.1173544",

language = "English",

series = "Proceedings - 5th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2002",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2--8",

editor = "Wanlei Zhou and Andrzej Goscinski and Guo-jie Li and Xue-bin Chi",

booktitle = "Proceedings - 5th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2002",

address = "United States",

}