Approximate Selection with Unreliable Comparisons in Optimal Expected Time
share
Given n elements, an integer k and a parameter ε, we study to select 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. In this fault model, the fundamental problems of finding the minimum, selecting the k-th smallest element and sorting have been shown to require Θ(n log1/Q), Θ(nlogmin{k,n-k}/Q) and Θ(nlogn/Q) comparisons, respectively, to achieve success probability 1-Q. Recently, Leucci and Liu proved that the approximate minimum selection problem (k=0) requires expected Θ(ε^-1log1/Q) comparisons. We develop a randomized algorithm that performs expected O(k/nε^-2log1/Q) comparisons to achieve success probability at least 1-Q. We also prove that any randomized algorithm with success probability at least 1-Q performs expected Ω(k/nε^-2log1/Q) comparisons. Our results indicate a clear distinction between approximating the minimum and approximating the k-th smallest element, which holds even for the high probability guarantee, e.g., if k=n/2 and Q=1/n, Θ(ε^-1log n) versus Θ(ε^-2log n). Moreover, if ε=n^-α for α∈ (0,1/2), the asymptotic difference is almost quadratic, i.e., Θ̃(n^α) versus Θ̃(n^2α).
READ FULL TEXT