Approximate Selection with Unreliable Comparisons in Optimal Expected Time

Abstract

Given $n$ elements, an integer $k$ and a parameter $\epsilon$, we study to select an element with rank in $(k-n\epsilon ,k+n\epsilon ]$ 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 $\Theta \left(n\log \frac{1}{Q}\right)$, $\Theta \left(n\log \frac{\min \{k,n-k\}}{Q}\right)$ and $\Theta \left(n\log \frac{n}{Q}\right)$ comparisons, respectively, to achieve success probability $1-Q$. Recently, Leucci and Liu proved that the approximate minimum selection problem ($k=0$) requires expected $\Theta ({\epsilon }^{-1}\log \frac{1}{Q})$ comparisons. We develop a randomized algorithm that performs expected $O(\frac{k}{n}{\epsilon }^{-2}\log \frac{1}{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 $\Omega (\frac{k}{n}{\epsilon }^{-2}\log \frac{1}{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=\frac{n}{2}$ and $Q=\frac{1}{n}$, $\Theta ({\epsilon }^{-1}\log n)$ versus $\Theta ({\epsilon }^{-2}\log n)$. Moreover, if $\epsilon =n^{-\alpha }$ for $\alpha \in (0,\frac{1}{2})$, the asymptotic difference is almost quadratic, i.e., $\tilde{\Theta }(n^{\alpha })$ versus $\tilde{\Theta }(n^{2\alpha })$.