TY - JOUR
T1 - On computing an optimal permutation of ranks for multiselection
AU - Al-Suwaiyel, Muhammad Hamad Mohammed
PY - 2010
Y1 - 2010
N2 - Given a set of n elements, and a sorted sequence K = k(1), k(2), ..., k(r) of positive integers between 1 and n, it is required to find the kith smallest element for all values of i, 1 <= i <= r. We present a dynamic programming algorithm for computing an optimal permutation of the input ranks that results in the least number of comparisons when used as a preprocessing step with any algorithm that uses repetitive calls to an algorithm for selection. The running time of the proposed algorithm is 0(r(3)). (C) 2010 Elsevier Ltd. All rights reserved.
AB - Given a set of n elements, and a sorted sequence K = k(1), k(2), ..., k(r) of positive integers between 1 and n, it is required to find the kith smallest element for all values of i, 1 <= i <= r. We present a dynamic programming algorithm for computing an optimal permutation of the input ranks that results in the least number of comparisons when used as a preprocessing step with any algorithm that uses repetitive calls to an algorithm for selection. The running time of the proposed algorithm is 0(r(3)). (C) 2010 Elsevier Ltd. All rights reserved.
M3 - Article
SN - 0898-1221
JO - Computers and Mathematics with Applications
JF - Computers and Mathematics with Applications
ER -