On computing an optimal permutation of ranks for multiselection

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.