@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",
}