无线网络中的会议呼叫搜索问题研究

### 无线网络中的会议呼叫搜索问题研究 在无线网络的会议呼叫搜索场景中，存在着不同的搜索协议，如遗忘搜索协议和半自适应搜索协议。遗忘搜索协议的最优解问题是NP - 难的，而半自适应搜索协议在特定情况下是多项式可解的。下面我们将详细探讨遗忘搜索问题的NP - 难性以及针对该问题的多项式时间近似方案（PTAS）。 #### 1. 遗忘搜索问题的NP - 难性 在之前的研究中，Bar - Noy和Naor证明了在$B = 1$且$d = m = 2$的情况下，寻找最优遗忘搜索协议是NP - 难的。现在我们将这个结果扩展到一般的紧密情况。 **定理1**：即使限制在$d = m$轮且$B = 1$的紧密实例中，对于所有固定的$d\geq2$值，寻找最优遗忘搜索协议也是NP - 难的。 **证明思路**： - 对于$d = m = 2$的情况已有前人证明。对于$d\geq3$的情况，我们通过从划分问题进行归约来证明。划分问题是给定$N$个整数$a(1),\cdots,a(N)$，使得$\sum_{i = 1}^{N}a(i)=2S$（$S\geq2$为整数），问题是是否存在子集$J\in\{1,\cdots,N\}$，使得$\sum_{i\in J}a(i)=S$。 - 我们构造一个遗忘搜索问题的实例： - 设$\delta>0$是一个小的正值，且$\delta<\frac{1}{8S^{2}d^{2}}$。有$N + m - 2$个单元$c_1,\cdots,c_{N + m - 2}$。 - 前两个用户在单元$c_j$（$j\leq N$）的概率为$p_{1,j}=p_{2,j}=\frac{(1 - \delta)a(j)}{2S}$，在单元$j > N$的概率为$p_{1,j}=p_{2,j}=\frac{\delta}{m - 2}$。 - 对于其他$m - 2$个用户，用户$i$（$3\leq i\leq m$）在单元$i + N - 2$的概率为$1 - \delta$，在其他单元$j\neq i + N - 2$的概率为$\frac{\delta}{N + m - 3}$。 - **存在精确划分的情况**： - 若存在精确划分，设$J$是满足$\sum_{i\in J}a(i)=S$的子集。在第一轮，询问$J$中的单元关于第一个用户，询问$\{1,\cdots,N\}-J$中的单元关于第二个用户，其他单元$N + k$询问用户$k + 2$。 - 第一个用户和第二个用户在第一轮被找到的概率均为$\frac{1 - \delta}{2}$，其他用户在第一轮被找到的概率为$1 - \delta$。所有用户在第一轮被找到的概率为$\frac{(1 - \delta)^{m}}{4}$，第二轮搜索的概率为$1-\frac{(1 - \delta)^{m}}{4}$。所有用户在前两轮被找到的概率至少为$(1 - \delta)^{m}$，搜索持续至少三轮（最多$m$轮）的概率至多为$1-(1 - \delta)^{m}$。 - 总搜索成本至多为$n + n(1-\frac{(1 - \delta)^{m}}{4})+n(m - 2)(1-(1 - \delta)^{m})\leq\frac{7n}{4}+nm^{2}\delta<\frac{7n}{4}+\frac{n}{8S^{2}}$。 - **不存在精确划分的情况**： - 若不存在精确划分，对于任意子集$J'\subseteq\{1,\cdots,N\}$，要么$\sum_{i\in J'}a(i)\leq S - 1$，要么$\sum_{i\in J'}a(i)\geq S + 1$。 - 若$N + 1,\cdots,N + m - 2$中有单元在第一轮未被询问其对应概率为$1 - \delta$的用户，第二轮搜索的概率至少为$1 - \delta$，成本至少为$2n - n\delta$。 - 否则，考虑单元$1,\cdots,N$，设$A_1\subseteq\{1,\cdots,N\}$是第一轮询问第一个用户的单元子集，$A_2\subseteq\{1,\cdots,N\}$是第一轮询问第二个用户的单元子集。则$p(1)+p(2)\leq1 - \delta$，其中$p(1)=\sum_{j\in A_1}p_{1,j}$，$p(2)=\sum_{j\in A_2}p_{2,j}$。 - 由于不存在精确划分，到达第二轮的概率至少为$1-(1 - \delta)^{2}\frac{S^{2}-1}{4S^{2}}$，成本至少为$n + n(1-\frac{S^{2}-1}{4S^{2}}(1 - \delta)^{2})\geq n + n(1-\frac{S^{2}-1}{4S^{2}})=\frac{7n}{4}+\frac{n}{4S^{2}}$。 综上，若存在精确划分，最优成本至多为$\frac{7n}{4}+\frac{n}{8S^{2}}$；若不存在精确划分，最优成本至少为$\frac{7n}{4}+\frac{n}{4S^{2}}$。因此，判断成本是否至多为$\frac{7n}{4}+\frac{3n}{16S^{2}}$是NP - 难的。 此外，若$d$不是固定值，而是输入的一部分，该问题会变成强NP - 难问题。 **定理2**：即使限制在$d = m$轮且$B = 1$的紧密实例中，寻找最优遗忘搜索协议也是强NP - 难的。 #### 2. 遗忘搜索问题的多项式时间近似方案（PTAS） 我们假设每个用户和单元对的概率非零。在这种情况下，每一轮每个单元必须恰好针对一个用户进行询问，所以每个单元需要分配一个用户的排列。由于我们处理的是紧密实例，第一轮的成本已经是$n$，所以$OPT\geq n$。 我们设$0 < \varepsilon<\frac{1}{(20m)^{m + 1}\cdot m!}$，下面将分别针对两个用户和$m$个用户的情况介绍PTA