On computing an optimal permutation of ranks for multiselection

Given a set of nn elements, and a sorted sequence K=k1,k2,…,krK=k1,k2,…,kr of positive integers between 1 and nn, it is required to find the kikith smallest element for all values of i,1≤i≤ri,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)O(r3).