Approximate selection with unreliable comparisons in sublinear time
Journal
Journal of Computer and System Sciences
Journal Volume
155
Start Page
103699
ISSN
0022-0000
Date Issued
2026-02
Author(s)
Abstract
Given n elements, an integer [Formula presented] and a parameter [Formula presented], we study the problem of selecting an element with rank in (k−nε,k+nε] 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. We develop a randomized algorithm that performs expected [Formula presented] comparisons to achieve success probability at least 1−Q. We also prove that even in the absence of comparison faults, any randomized algorithm with success probability at least 1−Q performs expected [Formula presented] comparisons. In particular, our algorithm is optimal as long as n is large enough, i.e., when [Formula presented]; outside this parameter range, no algorithm performs a sublinear number of comparisons. Surprisingly, for constant Q, our algorithm performs expected [Formula presented] comparisons with and without comparison faults, while for the exact selection problem, the expected number of comparisons is Θ(nlogk) with faults versus Θ(n) without faults.
Publisher
Elsevier BV
Type
journal article