Almost Optimal Explicit Selectors
Almost Optimal Explicit Selectors
复制标题
几乎最优的显式选择器
DOI：
10.1007/11537311_24
复制
发表时间：
2005
影响因子：
4.9
通讯作者：
D. Kowalski
中科院分区：
文献类型：
--
作者：
Bogdan S. Chlebus;D. Kowalski
我们将交集选择理解为通过一个集合中的单个元素在另一个集合中出现的唯一性来区分它。更精确地说，给定两个集合A和B，如果A ≠ B = {z}，则元素z∈ A被集合B选择。选择器是这样的家庭$\mathcal{S}$的集合B的一些域，允许选择许多元素从足够小的子集A的域。选择器用于多路访问信道的通信协议、无线电网络中分布式计算原语的实现以及组测试的算法中。我们给出了新的显式（n，k，r）-选择子，其大小为$\mathcal{O}（min [n，\frac{k^2}{k-r+1} polylog~n]）$，对任意参数r ≤ k ≤ n.我们建立了一个关于（n，k，r）-选择器长度的下界$\Omega（min [n，\frac{k^2}{k-r+1} \cdot \frac{log（n/k）}{log（k/（k-r+1））}]）$，这表明我们的构造在一个接近最优的polylog n因子内。新的选择器被应用于开发明确的实现选择决议的多址信道上，在无线电网络中的闲聊和一个算法的组测试与抑制剂。
We understand selection by intersection as distinguishing a single element of a set by the uniqueness of its occurrence in some other set. More precisely, given two sets A and B, if A ∩ B = {z}, then element z∈ A is selected by set B. Selectors are such families $\mathcal{S}$ of sets B of some domain that allow to select many elements from sufficiently small subsets A of the domain. Selectors are used in communication protocols for the multiple-access channel, in implementations of distributed-computing primitives in radio networks, and in algorithms for group testing. We give new explicit (n,k,r)-selectors of size $\mathcal{O}(min [n, \frac{k^2}{k-r+1} polylog~n])$, for any parameters r ≤ k ≤ n. We establish a lower bound $\Omega(min [n, \frac{k^2}{k-r+1} \cdot \frac{log(n/k)}{log(k/(k-r+1))}])$ on the length of (n,k,r)-selectors, which demonstrates that our construction is within a polylog n factor close to optimal. The new selectors are applied to develop explicit implementations of selection resolution on the multiple-access channel, gossiping in radio networks and an algorithm for group testing with inhibitors.