...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Duality Codes and the Integrality Gap Bound for Index Coding
【24h】

Duality Codes and the Integrality Gap Bound for Index Coding

机译：对偶码和索引编码的完整性缺口

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper considers a base station that delivers packets to multiple receivers through a sequence of coded transmissions. All receivers overhear the same transmissions. Each receiver may already have some of the packets as side information, and requests another subset of the packets. This problem is known as the index coding problem and can be represented by a bipartite digraph. An integer linear program is developed that provides a lower bound on the minimum number of transmissions required for any coding algorithm. Conversely, its linear programming relaxation is shown to provide an upper bound that is achievable by a simple form of vector linear coding. Thus, the information theoretic optimum is bounded by the integrality gap between the integer program and its linear relaxation. In the special case, when the digraph has a planar structure, the integrality gap is shown to be zero, so that exact optimality is achieved. Finally, for nonplanar problems, an enhanced integer program is constructed that provides a smaller integrality gap. The dual of this problem corresponds to a more sophisticated partial clique coding strategy that time-shares between maximum distance separable codes. This paper illuminates the relationship between index coding, duality, and integrality gaps between integer programs and their linear relaxations.
机译：本文考虑了一种基站，该基站通过一系列编码传输将数据包传递给多个接收器。所有接收器都监听相同的传输。每个接收器可能已经具有一些分组作为辅助信息，并且请求分组的另一子集。这个问题被称为索引编码问题，可以用二部图表示。开发了整数线性程序，该程序为任何编码算法所需的最小传输次数提供了下限。相反，它的线性编程松弛被显示为提供了一个上限，该上限可以通过向量线性编码的简单形式来实现。因此，信息理论上的最优值被整数程序与其线性松弛之间的完整性差距所限制。在特殊情况下，当有向图具有平面结构时，完整性间隙显示为零，因此可以实现精确的最优性。最后，对于非平面问题，构建了一个增强的整数程序，该程序提供了较小的完整性差距。此问题的对偶对应于更复杂的部分集团编码策略，该策略在最大距离可分离代码之间分时共享。本文阐述了整数程序之间的索引编码，对偶性和完整性缺口及其线性松弛之间的关系。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号