Optimal parallel weighted multiselection
Date
2002
Authors
Shen, H.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
2002 IEEE Region 10 International Conference on Computers, Communications, Control and Power Engineering : IEEE TENCOM'02 : October 28-31, 2002, Beijing, China / Yuan Baozong, Tang Xiaofang (eds.) ; sponsored by IEEE Region 10 ; co-sponsored by IEEE Computer Society Beijing Chapter ; organized by IEEE Beijing Section ; supported by Chinese Institute of Electronics (CIE) ... [et al], pp. 323-326.
Statement of Responsibility
Hong Shen
Conference Name
TENCOM 2002 (2002 : Beijing, China)
Abstract
Weighted multiselection requires us to select r elements from a given set of n elements, each associated with a weight such that each element selected is on a pre-specified 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(nlogr) which is optimal. Our parallel algorithm runs in O(T/sub 1/logr) time on an EREW PRAM with 1 < p /spl les/ n processors, and is optimal with respect to T/sub 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 /spl les/ nloglogn/logn, and time-optimally in O(logn/loglogn) time for nloglogn/logn < p /spl les/ n.
School/Discipline
Dissertation Note
Provenance
Description
Copyright © 2002 IEEE