Approximate Minimum Selection with Unreliable Comparisons

We consider the approximate minimum selection problem in presence of independent random comparison faults. This problem asks to select one of the smallest k elements in a linearly-ordered collection of n elements by only performing unreliable pairwise comparisons: whenever two elements are compared, there is a small probability that the wrong comparison outcome is observed. We design a randomized algorithm that solves this problem with a success probability of at least [Formula: see text] for [Formula: see text] and any [Formula: see text] using [Formula: see text] comparisons in expectation (if [Formula: see text] or [Formula: see text] the problem becomes trivial). Then, we prove that the expected number of comparisons needed by any algorithm that succeeds with probability at least [Formula: see text] must be [Formula: see text] whenever q is bounded away from [Formula: see text] , thus implying that the expected number of comparisons performed by our algorithm is asymptotically optimal in this range. Moreover, we show that the approximate minimum selection problem can be solved using [Formula: see text] comparisons in the worst case, which is optimal when q is bounded away from [Formula: see text] and [Formula: see text] .