The double selection problem (Q1262124)

One of the most intensively investigated problems in combinatorial search theory is the selection problem. One searches for the minimal number \(V_ s(n)\) of pairwise comparisons required for determining the s-th largest element among an unknown order of n linearly ordered elements. The present paper investigates the related problem of locating both the s-th and the t-th element. The resulting quantity is denoted \(V_{t,s}(n).\) Two special cases of this problem are well known. The case \(s=1\), \(t=2\) asks for the largest element and the runner-up, and for this case a tight bound \(V_{1,2}(n)=(n-2)+\lceil \log (n)\rceil\) has been given by Kislitsyn. The case of determining both the largest and the smallest element has been investigated by Ira Pohl: \(V_{1,n}(n)=\lceil 3n/2\rceil -2.\) The author derives by a potential method two general lower bounds, one of which is suitable for small s-t and another which provides reasonable results when s-t is large. For the cases \(t=s-1\) and \(t=s-2\) matching upper bounds are provided. Also for the case \(t=2\), \(s=n\) a close upper bound is obtained. It is shown that the required number of comparisons is always at least as large as for the known case \(t=1\), \(s=2\). A related problem, investigated by Varecza, is the determination of the required number of pairwise comparisons required for verifying that a given pair a, b indeed is the solution of the s,t selection problem. For this related problem bounds are provided as well. The author finishes with a conjecture due to Hastad stating that the selection of a pair of adjacent elements is asymptotically as difficult as selecting the first of these elements. If true this conjecture, in combination with the bounds in this paper, would prove a lower bound of 2n-o(n) for the median problem. The best lower bound for this problem so far, according to the author is 1.75n-o(n). It should be noted that for this problem an improved lower bound of \(79n/43+O(1)\) is listed in \textit{G. H. Gonnet}'s Handbook of algorithms and data structures (Addision-Wesley 1984; Zbl 0665.68001). Previously an lower bound \(11n/6+O(1)\) had been claimed by C. K. Yap.