A Polynomial-Time Algorithm for Pliable Index Coding
A Polynomial-Time Algorithm for Pliable Index Coding
复制标题
柔韧索引编码的多项式时间算法
DOI：
10.1109/tit.2017.2752088
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
C. Fragouli
中科院分区：
文献类型：
--
作者：
Linqi Song;C. Fragouli
在柔韧索引编码中，我们考虑一个具有 <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> 消息和 <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> 客户端的服务器，其中每个客户端都有消息子集作为辅助信息。我们力求最大限度地减少广播传输的数量，以便每个客户端都可以恢复她尚未拥有的任何一条未知消息。先前的工作表明，柔韧索引编码问题是 NP 困难的，最多需要 <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(\log ^{2}(n))$ </tex-math></inline-formula> 广播传输，这表明在最坏情况下比传统索引编码需要指数级节省 <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(n)$ </tex-math></inline-formula> 传输。在本文中，基于我们提出的解码标准，我们首先设计了一种确定性多项式时间算法，该算法可以在最坏的情况下实现由 <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(\log ^{2}(n))$ </tex-math></inline-formula> 广播传输限制的性能上限，从而实现指数级收益。我们将算法扩展到 <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula>-requests 情况，其中每个客户端都需要 <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> 她没有的未知消息，并表明我们的算法最多需要 <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(t\log (n)+\log ^{2}(n))$ </tex-math></inline-formula> 广播传输。我们构建的下界实例至少需要 <inline-formula> <tex-math notation="LaTeX">$\Omega (\log (n))$ </tex-math></inline-formula> 传输用于线性柔韧索引编码，并且至少需要 <inline-formula> <tex-math notation="LaTeX">$\Omega (t+\log (n))$ </tex-math></inline-formula> 传输对于 <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula>-requests 情况，表明我们的上限和下限都是 <inline-formula> <tex-math notation="LaTeX">$\log (n)$ </tex-math></inline-formula> 的多项式，并且相差 <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(\log (n))$ </tex-math></inline-formula>。我们对随机实例进行了概率分析，结果表明，与 <inline-formula> <tex-math notation="LaTeX">$\Theta (n/\log (n))$ 相比，所需的传输次数几乎肯定是 <inline-formula> <tex-math notation="LaTeX">$\Theta (\log (n))$ </tex-math></inline-formula> </tex-math></inline-formula> 用于索引编码。此外，我们表明这些上限和下限也适用于最坏情况实例和随机图实例中的向量柔韧索引编码，这意味着向量编码在这些界限方面没有提供好处。我们的数值实验表明，我们的算法优于现有的柔韧索引编码算法，传输量减少了 50%。
In pliable index coding, we consider a server with <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> messages and <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> clients, where each client has as side information a subset of the messages. We seek to minimize the number of broadcast transmissions, so that each client can recover any one unknown message she does not already have. Previous work has shown that the pliable index coding problem is NP-hard and requires at most <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(\log ^{2}(n))$ </tex-math></inline-formula> broadcast transmissions, which indicates exponential savings over the conventional index coding that requires in the worst case <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(n)$ </tex-math></inline-formula> transmissions. In this paper, building on a decoding criterion that we propose, we first design a deterministic polynomial-time algorithm that can realize the exponential benefits, by achieving, in the worst case, a performance upper bounded by <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(\log ^{2}(n))$ </tex-math></inline-formula> broadcast transmissions. We extend our algorithm to the <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula>-requests case, where each client requires <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> unknown messages that she does not have, and show that our algorithm requires at most <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(t\log (n)+\log ^{2}(n))$ </tex-math></inline-formula> broadcast transmissions. We construct lower bound instances that require at least <inline-formula> <tex-math notation="LaTeX">$\Omega (\log (n))$ </tex-math></inline-formula> transmissions for linear pliable index coding and at least <inline-formula> <tex-math notation="LaTeX">$\Omega (t+\log (n))$ </tex-math></inline-formula> transmissions for the <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula>-requests case, indicating that both our upper and lower bounds are polynomials of <inline-formula> <tex-math notation="LaTeX">$\log (n)$ </tex-math></inline-formula> and differ within a factor of <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(\log (n))$ </tex-math></inline-formula>. We provide a probabilistic analysis over random instances and show that the required number of transmissions is almost surely <inline-formula> <tex-math notation="LaTeX">$\Theta (\log (n))$ </tex-math></inline-formula>, as compared with the <inline-formula> <tex-math notation="LaTeX">$\Theta (n/\log (n))$ </tex-math></inline-formula> for index coding. In addition, we show that these upper and lower bounds also hold for vector pliable index coding in the worst case instances and the random graph instances, implying that vector coding does not provide benefits in terms of these bounds. Our numerical experiments show that our algorithm outperforms existing algorithms for pliable index coding by up to 50% less transmissions.
随机图的 Minrank
影响因子：
2.5
作者：
Golovnev, Alexander;Regev, Oded;Weinstein, Omri
通讯作者：
Weinstein, Omri