On computing an optimal permutation of ranks for multiselection

Given a set of n elements, and a sorted sequence K = k1, k2, . . . , kr 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 O(r3).