The double selection problem

AbstractOne of the best studied problems in combinatorial search theory concerns the selection of the sth largest element out of an unknown linear order. In this paper, the corresponding problem, how to find the sth and tth largest elements, is treated. Two general lower bounds and some upper bounds are derived, and it is shown that an algorithm selecting any two elements (whatever their positions) can never be faster than selection of the top two elements, thereby answering a question of G. Katona. Some remarks on recognition and asymptotics are added