Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate
Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate
复制标题
带辅助信息的广播：限制和近似广播速率
DOI：
--
复制
发表时间：
2013
影响因子：
2.5
通讯作者：
E. Lubetzky
中科院分区：
文献类型：
--
作者：
A. Błasiak;Robert D. Kleinberg;E. Lubetzky
索引编码最近受到相当大的关注，部分是由于诸如无线网络中的快速视频点播和高效通信之类的应用，部分是由于其与网络编码的联系。在各种环境下研究了最佳编码方案和有效的算法，同时也为网络编码带来了新的结果，例如改善了线性和非线性容量之间的差距以及近似的难度。带边信息的广播问题是索引编码问题的一个推广，它从发送者和用户集以及消息集开始。每个用户拥有消息的子集，并希望从集合中获得额外的消息。发送者希望广播一条消息，以便每个用户在接收到广播时可以计算出她想要的消息。感兴趣的基本参数是广播速率β，即足够长的广播的平均通信成本。虽然Bar-Yossef（2006）、Lubetzky and Stav（2007）、Alon（2008）和Blasiak（2011）提出了许多新的非平凡β边界，但没有已知的多项式时间算法来近似非平凡因子内的β，并且对于所有非平凡情况，β的确切值仍然未知。使用Blasiak（2011）中介绍的信息论线性规划，我们给出了一个多项式时间算法，用于识别β = 2的实例，并精确地确定各种图类的β（例如，循环群的各种Cayley图）。进一步，扩展Ramsey理论的思想，我们给出了一个计算β的多项式时间算法，该算法具有非平凡的逼近比.最后，我们通过给出显示β与相应边界之间的分离的构造来洞察先前边界的质量。特别地，我们构造了β是一致有界的图，而从朴素编码方案导出的上界是多项式差的。
Index coding has received considerable attention recently motivated in part by applications such as fast video-on-demand and efficient communication in wireless networks and in part by its connection to network coding. Optimal encoding schemes and efficient heuristics were studied in various settings, while also leading to new results for network coding such as improved gaps between linear and non-linear capacity as well as hardness of approximation. The problem of broadcasting with side information, a generalization of the index coding problem, begins with a sender and sets of users and messages. Each user possesses a subset of the messages and desires an additional message from the set. The sender wishes to broadcast a message so that on receipt of the broadcast each user can compute her desired message. The fundamental parameter of interest is the broadcast rate, β, the average communication cost for sufficiently long broadcasts. Though there have been many new nontrivial bounds on β by Bar-Yossef (2006), Lubetzky and Stav (2007), Alon (2008), and Blasiak (2011) there was no known polynomial-time algorithm for approximating β within a nontrivial factor, and the exact value of β remained unknown for all nontrivial instances. Using the information theoretic linear program introduced in Blasiak (2011), we give a polynomial-time algorithm for recognizing instances with β = 2 and pinpoint β precisely for various classes of graphs (e.g., various Cayley graphs of cyclic groups). Further, extending ideas from Ramsey theory, we give a polynomial-time algorithm with a nontrivial approximation ratio for computing β. Finally, we provide insight into the quality of previous bounds by giving constructions showing separations between β and the respective bounds. In particular, we construct graphs where β is uniformly bounded while its upper bound derived from the naïve encoding scheme is polynomially worse.