Fast Approximate Rank Determination and Selection with Group Testing

Suppose that a group test operation is available for checking order relations in a set, can this speed up problems like finding the minimum/maximum element, rank determination and selection? We consider a one-sided group test to be available, where queries are of the form u ≤Q V or V ≤Q u, and the answer is `yes' if and only if there is some v ∈ V such that u ≤ v or v ≤ u, respectively. We restrict attention to total orders and focus on query-complexity; for min or max finding, we give a Las Vegas algorithm that makes O(log² n) expected queries. We also give randomized approximate algorithms for rank determination and selection; we allow a relative error of 1 ± δ for $δ> 0$ in the estimated rank or selected element. In this case, we give a Monte Carlo algorithm for approximate rank determination with expected query complexity Õ(1/δ² - log ε), where $1-ε$ is the probability that the algorithm succeeds. We also give a Monte Carlo algorithm for approximate selection that has expected query complexity Õ(-log( εδ²) / δ⁴); it has probability at least 1/2 to output an element x, and if so, x has the desired approximate rank with probability $1-ε$.