An Efficient Approximate Algorithm for the k-th Selection Problem

We present an efficient randomized algorithm for the approximate k-th selection problem. It works in-place and it is fast and easy to implement. The running time is linear in the length of the input. For a large input set the algorithm returns, with high probability, an element which is very close to the exact k-th element. The quality of the approximation is analyzed theoretically and experimentally