Approximate Selection with Unreliable Comparisons in Optimal Expected Time

Shengyu Huang, Chih-Hung Liu, Daniel Rutschman

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 th…