标题： 快速近似秩确定与分组测试选择 显示英文标题

标题： Fast Approximate Rank Determination and Selection with Group Testing

摘要： 假设有一个组测试操作可用于检查集合中的顺序关系，这是否能加快寻找最小/最大元素、等级确定和选择等问题的速度？ 我们考虑可用一个单边组测试，其中查询的形式为$u \le_Q V$或$V \le_Q u$，当且仅当存在某个$v \in V$使得$u \le v$或$v \le u$时，答案为“是”。 我们仅关注全序关系并专注于查询复杂度；对于最小值或最大值查找，我们给出一个拉斯维加斯算法，其预期查询次数为$\mathcal{O}(\log^2 n)$。 我们还给出了用于秩确定和选择的随机近似算法；我们允许估计的秩或选定元素中的相对误差为$1 \pm \delta$对于$\delta > 0$。 在这种情况下，我们给出一个蒙特卡洛算法用于近似秩确定，其期望查询复杂度为$\tilde{\mathcal{O}}(1/\delta^2 - \log \epsilon)$，其中$1-\epsilon$是该算法成功的概率。 我们还给出一个用于近似选择的蒙特卡洛算法，其期望查询复杂度为$\tilde{\mathcal{O}}(-\log( \epsilon \delta^2) / \delta^4)$; 它以至少$\frac{1}{2}$的概率输出一个元素$x$，并且如果这样，$x$以$1-\epsilon$的概率具有所需的近似排名。 显示英文摘要

摘要： 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 \le_Q V$ or $V \le_Q u$, and the answer is `yes' if and only if there is some $v \in V$ such that $u \le v$ or $v \le 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 $\mathcal{O}(\log^2 n)$ expected queries. We also give randomized approximate algorithms for rank determination and selection; we allow a relative error of $1 \pm \delta$ for $\delta > 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 $\tilde{\mathcal{O}}(1/\delta^2 - \log \epsilon)$, where $1-\epsilon$ is the probability that the algorithm succeeds. We also give a Monte Carlo algorithm for approximate selection that has expected query complexity $\tilde{\mathcal{O}}(-\log( \epsilon \delta^2) / \delta^4)$; it has probability at least $\frac{1}{2}$ to output an element $x$, and if so, $x$ has the desired approximate rank with probability $1-\epsilon$.