Approximate Selection with Unreliable Comparisons in Sublinear Time

Given n elements, an integer k ≤ n/2 and a parameter ε ≥ 1/n , we study the problem of selecting an element with rank in (k − nε, k + nε] using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant error probability, and multiple comparisons between the same pair of elements are independent. We develop a randomized algorithm that performs expected O(k/nε⁻² log 1/Q) comparisons to achieve success probability at least 1−Q . We also prove that even in the absence of comparison faults, any randomized algorithm with success probability at least 1-Q performs expected Ω(︁min{n, k/n ε⁻² log 1/Q })︁ comparisons. In particular, our algorithm is optimal as long as n is large enough, i.e., when n = Ω(︂ k/n ε⁻² log 1/Q)︂ ; outside this parameter range, no algorithm performs a sublinear number of comparisons. Surprisingly, for constant Q, our algorithm performs expected O(k/n ε⁻²) comparisons with and without comparison faults, while for the exact selection problem, the expected number of comparisons is Θ (n log k) with faults versus Θ (n) without faults.