• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate
【24h】

Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate

机译：具有辅助信息的广播：限制和近似广播速率

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

摘要

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 polynomia- ly worse.
机译：最近，索引编码受到了相当大的关注，部分原因是诸如无线网络中的快速视频点播和高效通信之类的应用，以及部分由于其与网络编码的连接。在各种环境下研究了最佳编码方案和有效的启发式方法，同时还为网络编码带来了新的结果，例如改善了线性和非线性能力之间的差距以及近似硬度。附带信息广播的问题，即索引编码问题的概括，始于发送方以及用户和消息集。每个用户拥有消息的一个子集，并希望从集合中获得一条附加消息。发送者希望广播一条消息，以便每个用户在接收到广播后都可以计算出所需的消息。感兴趣的基本参数是广播速率β，即足够长的广播的平均通信成本。尽管Bar-Yossef（2006），Lubetzky和Stav（2007），Alon（2008）和Blasiak（2011）在β上有许多新的非平凡边界，但尚无已知的在非平凡因子内逼近β的多项式时间算法，对于所有非平凡实例，β的确切值仍然未知。使用Blasiak（2011）中引入的信息理论线性程序，我们提供了多项式时间算法来识别具有β= 2的实例并精确定位各种图类（例如各种循环群的Cayley图）的β。此外，从拉姆齐理论的思想出发，我们给出了具有非平凡逼近比的多项式时间算法来计算β。最后，我们通过给出表示β与各个范围之间分隔的构造，提供对先前范围质量的洞察。尤其是，我们构造了图，其中β是有界的，而其朴素的编码方案的上界在多项式上更差。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号