A Deterministic Algorithm for Pliable Index Coding
A Deterministic Algorithm for Pliable Index Coding
复制标题
一种用于柔韧索引编码的确定性算法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
C. Fragouli
中科院分区：
文献类型：
--
作者：
Linqi Song;C. Fragouli
柔性索引编码考虑具有m个消息的服务器和n个客户端，其中每个客户端具有消息的子集作为边信息。我们寻求最小化服务器应该进行的传输次数，以便每个客户端接收到她还没有的（任何）一条消息。以前的工作已经表明，服务器可以使用O（log^2（n））传输来实现这一点，并且在最坏的情况下至少需要Omega（log（n））传输，但是找到最佳长度的代码是NP难的。在本文中，我们提出了一个确定性的算法，我们证明达到这个上限，也就是说，在一个顺序几乎作为最坏情况下的最佳代码长度。我们还建立了一个柔韧的索引编码问题和minrank问题之间的连接在一个家庭的混合矩阵。
Pliable index coding considers a server with m messages, and n clients where each has as side information a subset of the messages. We seek to minimize the number of transmissions the server should make, so that each client receives (any) one message she does not already have. Previous work has shown that the server can achieve this using O(log^2(n)) transmissions and needs at least Omega(log(n)) transmissions in the worst case, but finding a code of optimal length is NP-hard. In this paper, we propose a deterministic algorithm that we prove achieves this upper bound, that is, in an order almost as the worst-case optimal code length. We also establish a connection between the pliable index coding problem and the minrank problem over a family of mixed matrices.