Optimal parallel weighted multiselection

Research output: Contribution to conferencePaperpeer-review

1 Citation (Scopus)

Abstract

Weighted multiselection requires 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 BREW PRAM. Our sequential algorithm solves this problem in time O(n log r) which is optimal. Our parallel algorithm runs in O(T1 log r) time on an EREW PRAM with 1< p ≤ n processors, and is optimal with respect to T1 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 ≤ 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.

Original languageEnglish
Pages323-326
Number of pages4
Publication statusPublished - 2002
Externally publishedYes
Event2002 IEEE Region 10 Conference on Computers, Communications, Control and Power Engineering - Beijing, China
Duration: 28 Oct 200231 Oct 2002

Conference

Conference2002 IEEE Region 10 Conference on Computers, Communications, Control and Power Engineering
Country/TerritoryChina
CityBeijing
Period28/10/0231/10/02

Keywords

  • EREW PRAM
  • Multiselection
  • Parallel algorithm
  • Selection
  • Sorting
  • Weight selection

Fingerprint

Dive into the research topics of 'Optimal parallel weighted multiselection'. Together they form a unique fingerprint.

Cite this