论文标题
多党选择
Multiparty Selection
论文作者
论文摘要
给定一个序列$ a $ n $数字和一个整数（目标）参数$ 1 \ leq i \ leq n $，（确切的）选择问题要求在$ a $中找到$ i $ th的最小元素。据说元素是$（i，j）$ - 平庸的，如果它既不是$ i $的$ i $，也不是$ s $的底部$ j $元素。大约选择问题要求找到$（i，j）$ - 一些给定$ i，j $的中等元素；因此，该变体允许算法返回规定范围内的任何元素。在第一部分中，我们在Andrew Yao（1979）引入的两党模型中重新审视了选择问题，然后将精确选择的研究扩展到多方模型。在第二部分中，我们推断出近似选择中产生的一些交流复杂性好处。特别是，我们提出了一个确定性协议，用于在$ k $播放器中找到大约中位数。
Given a sequence $A$ of $n$ numbers and an integer (target) parameter $1\leq i\leq n$, the (exact) selection problem asks to find the $i$-th smallest element in $A$. An element is said to be $(i,j)$-mediocre if it is neither among the top $i$ nor among the bottom $j$ elements of $S$. The approximate selection problem asks to find a $(i,j)$-mediocre element for some given $i,j$; as such, this variant allows the algorithm to return any element in a prescribed range. In the first part, we revisit the selection problem in the two-party model introduced by Andrew Yao (1979) and then extend our study of exact selection to the multiparty model. In the second part, we deduce some communication complexity benefits that arise in approximate selection. In particular, we present a deterministic protocol for finding an approximate median among $k$ players.
