论文标题
在最佳预期时间中进行不可靠的比较的近似选择
Approximate Selection with Unreliable Comparisons in Optimal Expected Time
论文作者
论文摘要
给定的$ n $元素，整数$ k $和一个参数$ \ varepsilon $，我们研究使用$（k-n \ varepsilon，k+n \ varepsilon] $进行排名的元素，使用每个比较的结果是独立地与恒定的错误概率相比，与多个相同的构图相同的问题，该元素是独立的，该元素是独立于构建元素的元素。至少，选择$ k $ - 最小的元素和排序已被证明需要$θ\ big（n \ log \ frac {1} {q} {q} {q} \ big）$，$θ\ big（n \ log \ frac {\ frac {\ min \ min \ min \ { \ frac {n} {q} \ big）$比较，以实现成功概率$ 1-q $。 我们开发了一种随机算法，该算法执行预期$ O（\ frac {k} {n} \ varepsilon^{ - 2} \ log \ frac {1} {q} {q}）$比较以实现成功概率至少$ 1-q $。我们还证明，任何具有成功概率的随机算法至少$ 1-q $ permiss预期$ω（\ frac {k} {n} {n} \ varepsilon^{ - 2} \ log \ log \ frac {1} {1} {q} {q} {q}）$比较。我们的结果表明，在近似最小值和近似$ k $的最小元素之间有一个明确的区别，即使对于高概率保证，例如，例如，如果$ k = \ frac {n} {n} {2} $和$ q = \ frac {1} {1} {n} {n} {n} $θ（ $θ（\ varepsilon^{ - 2} \ log n）$。此外，如果$ \ varepsilon = n^{ - α} $ for $α\ in（0，0，\ frac {1} {2}）$，则渐近差几乎是二次的，即$ \tildeθ（n^α）$ vers $ \tildeθ（n^α）$ vers $ \ tildepilte $ \ \ tilde（n^n^al^al^al^}）。
Given $n$ elements, an integer $k$ and a parameter $\varepsilon$, we study to select an element with rank in $(k-n\varepsilon,k+n\varepsilon]$ 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. In this fault model, the fundamental problems of finding the minimum, selecting the $k$-th smallest element and sorting have been shown to require $Θ\big(n \log \frac{1}{Q}\big)$, $Θ\big(n\log \frac{\min\{k,n-k\}}{Q}\big)$ and $Θ\big(n\log \frac{n}{Q}\big)$ comparisons, respectively, to achieve success probability $1-Q$. Recently, Leucci and Liu proved that the approximate minimum selection problem ($k=0$) requires expected $Θ(\varepsilon^{-1}\log \frac{1}{Q})$ comparisons. We develop a randomized algorithm that performs expected $O(\frac{k}{n}\varepsilon^{-2} \log \frac{1}{Q})$ comparisons to achieve success probability at least $1-Q$. We also prove that any randomized algorithm with success probability at least $1-Q$ performs expected $Ω(\frac{k}{n}\varepsilon^{-2}\log \frac{1}{Q})$ comparisons. Our results indicate a clear distinction between approximating the minimum and approximating the $k$-th smallest element, which holds even for the high probability guarantee, e.g., if $k=\frac{n}{2}$ and $Q=\frac{1}{n}$, $Θ(\varepsilon^{-1}\log n)$ versus $Θ(\varepsilon^{-2}\log n)$. Moreover, if $\varepsilon=n^{-α}$ for $α\in (0,\frac{1}{2})$, the asymptotic difference is almost quadratic, i.e., $\tildeΘ(n^α)$ versus $\tildeΘ(n^{2α})$.
