Speeding up pairwise comparisons for large scale ranking and Selection

Classical sequential ranking-And-selection (R&S) procedures require all pairwise comparisons after collecting one additional observation from each surviving system, which is typically an O(k2) operation where k is the number of systems. When the number of systems is large (e.g., millions), these comparisons can be very costly and may significantly slow down the R&S procedures. In this paper we revise KN procedure slightly and show that one may reduce the computational complexity of all pairwise comparisons to an O(k) operation, thus significantly reducing the computational burden. Numerical experiments show that the computational time reduces by orders of magnitude even for moderate numbers of systems.