The double selection problem
type: Item
instance of: scholarly article
title: The double selection problem
zbMATH Open document ID: 0685.68038
DOI: 10.1016/0012-365X(88)90128-8
author: Martin Aigner
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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 \texti…
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4123292
zbMATH Keywords: partial order
zbMATH Keywords: comparison algorithm
zbMATH Keywords: selection problem
reviewed by: Peter van Emde Boas
MaRDI profile type: Publication
cites work: Producing posets
cites work: Selecting the top three elements
cites work: A Counting Approach to Lower Bounds for Selection Problems
cites work: Q5183260
cites work: Q5601827
cites work: Q3706485
cites work: A sorting problem and its complexity
cites work: Finding the median
cites work: Q3907568
cites work: Q3329473
cites work: Q3703300
description: scientific article; zbMATH DE number 4123292