论文标题
搜索，分类和蛋糕切成圆
Searching, Sorting, and Cake Cutting in Rounds
论文作者
论文摘要
我们研究以公平的分区问题激励的回合进行搜索和分类：鉴于$ n $玩家的蛋糕切割问题，请计算与玩家的$ k $回合互动的公平分配。在同时和完全自适应的设置之间插入插值，还捕获了平行的复杂性。我们发现，在圆圈中切割比例蛋糕等同于对综合的排名查询进行分类。我们设计了一轮比例切割的协议，而Alon和Azar给出了在带有等级查询的圆圈中进行排序的下限。受等级查询模型的启发，我们考虑了两个基本搜索问题：有序和无序搜索。 在未排序的搜索中，我们获得了一个数组$ \ vec {x} =（x_1，\ ldots，x_n）$和一个元素$ z $，承诺将以$ \ vec {x} $中的价格为$ \ vec {x} $。我们可以访问“甲骨文”，该甲骨文收到“位置$ i $的$ z $？”的疑问。并回答“是”或“否”。目的是找到$ z $的位置，并在与甲骨文的互动中至少在$ k $的互动中至少$ p $。 We show the expected query complexity of randomized algorithms on a worst case input is $np\bigl(\frac{k+1}{2k}\bigr) \pm O(1)$, while that of deterministic algorithms on a worst case input distribution is $np \bigl(1 - \frac{k-1}{2k}p \bigr) \pm o（1）$。这些边界甚至适用于完全自适应的无序搜索，随着阵列的大小，两个复杂性之间的比率收敛到$ 2-P $。 在有序搜索中，我们得到排序的数组$ \ vec {x} =（x_1，\ ldots，x_n）$和元素$ z $，承诺将以$ \ vec {x} $中的形式放在$ \ vec {x} $中。我们可以访问一个获得比较查询的甲骨文。在这里，我们发现在最坏情况下输入和确定性算法上，随机算法的预期查询复杂性基本相同：$ p k \ cdot n^{\ frac {\ frac {1} {k}} {k}} {k}} {k}} \ pm o（1+pk）$。
We study searching and sorting in rounds motivated by a fair division question: given a cake cutting problem with $n$ players, compute a fair allocation in at most $k$ rounds of interaction with the players. Rounds interpolate between the simultaneous and the fully adaptive settings, also capturing parallel complexity. We find that proportional cake cutting in rounds is equivalent to sorting with rank queries in rounds. We design a protocol for proportional cake cutting in rounds, while lower bounds for sorting in rounds with rank queries were given by Alon and Azar. Inspired by the rank query model, we then consider two basic search problems: ordered and unordered search. In unordered search, we get an array $\vec{x}=(x_1, \ldots, x_n)$ and an element $z$ promised to be in $\vec{x}$. We have access to an oracle that receives queries of the form "Is $z$ at location $i$?" and answers "Yes" or "No". The goal is to find the location of $z$ with success probability at least $p$ in at most $k$ rounds of interaction with the oracle. We show the expected query complexity of randomized algorithms on a worst case input is $np\bigl(\frac{k+1}{2k}\bigr) \pm O(1)$, while that of deterministic algorithms on a worst case input distribution is $np \bigl(1 - \frac{k-1}{2k}p \bigr) \pm O(1)$. These bounds apply even to fully adaptive unordered search, where the ratio between the two complexities converges to $2-p$ as the size of the array grows. In ordered search, we get sorted array $\vec{x}=(x_1, \ldots, x_n)$ and element $z$ promised to be in $\vec{x}$. We have access to an oracle that gets comparison queries. Here we find that the expected query complexity of randomized algorithms on a worst case input and deterministic algorithms on a worst case input distribution is essentially the same: $p k \cdot n^{\frac{1}{k}} \pm O(1+pk)$.
