  We consider the \emph{approximate minimum selection} problem in presence of
\emph{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 \emph{unreliable} pairwise comparisons: whenever two elements
are compared, there is a constant probability that the wrong answer is
returned.
  We design a randomized algorithm that solves this problem with probability
$1-q \in [ \frac{1}{2}, 1)$ and for the whole range of values of $k$ using $O(
\frac{n}{k} \log \frac{1}{q} )$ expected time. Then, we prove that the expected
running time of any algorithm that succeeds w.h.p. must be
$\Omega(\frac{n}{k}\log \frac{1}{q})$, thus implying that our algorithm is
asymptotically optimal, in expectation. These results are quite surprising in
the sense that for $k$ between $\Omega(\log \frac{1}{q})$ and $c \cdot n$, for
any constant $c<1$, the expected running time must still be
$\Omega(\frac{n}{k}\log \frac{1}{q})$ even in absence of comparison faults.
Informally speaking, we show how to deal with comparison errors without any
substantial complexity penalty w.r.t.\ the fault-free case. Moreover, we prove
that as soon as $k = O( \frac{n}{\log\log \frac{1}{q}})$, it is possible to
achieve the optimal \emph{worst-case} running time of $\Theta(\frac{n}{k}\log
\frac{1}{q})$.
