Three stories on a two-sided coin: Index coding, locally recoverable distributed storage, and guessing games on graphs
Three stories on a two-sided coin: Index coding, locally recoverable distributed storage, and guessing games on graphs
复制标题
双面硬币的三个故事：索引编码、本地可恢复的分布式存储和图上的猜谜游戏
DOI：
10.1109/allerton.2015.7447094
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Young
中科院分区：
文献类型：
--
作者：
Fatemeh Arbabjolfaei;Young
讨论了最近感兴趣的三个科学和工程问题--索引编码、局部可恢复分布式存储和图上的猜谜游戏，并阐明了它们的最优解之间的联系。推广了Shanmugam和Dimakis以及Mazumdar关于有向图上索引编码问题的最优广播速率与同一图上局部可恢复分布存储问题的归一化速率之间的互补性的最新结果，证明了这两个问题的容量域和最优速率域是互补的.建立这一结果的主要成分是Alon等人引入的混淆图的概念。(2008)，混淆图的顶点传递性，通过混淆图的分数色数刻画索引编码容量区域，以及通过混淆图的独立数刻画局部可恢复分布式存储的最优速率区域。作为互补性的第三个也是最后一个方面，Riis图上的猜谜游戏作为局部可恢复分布式存储问题的特例进行了讨论，证明了猜测博弈的最优策略的获胜概率以及最优策略的获胜概率与随机猜测的获胜概率之比可以分别由索引编码的容量域和分布式存储的最优速率域来表征。
Three science and engineering problems of recent interests - index coding, locally recoverable distributed storage, and guessing games on graphs - are discussed and the connection between their optimal solutions is elucidated. By generalizing recent results by Shanmugam and Dimakis and by Mazumdar on the complementarity between the optimal broadcast rate of an index coding problem on a directed graph and the normalized rate of a locally recoverable distributed storage problem on the same graph, it is shown that the capacity region and the optimal rate region of these two problems are complementary. The main ingredients in establishing this result are the notion of confusion graph introduced by Alon et al. (2008), the vertex transitivity of a confusion graph, the characterization of the index coding capacity region via the fractional chromatic number of confusion graphs, and the characterization of the optimal rate region of the locally recoverable distributed storage via the independence number of confusion graphs. As the third and final facet of the complementarity, guessing games on graphs by Riis are discussed as special cases of the locally recoverable distributed storage problem, and it is shown that the winning probability of the optimal strategy for a guessing game and the ratio between the winning probabilities of the optimal strategy and a random guess can be characterized, respectively, by the capacity region for index coding and the optimal rate region for distributed storage.
DOI：
10.1109/netcod.2013.6570823
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Baber R
通讯作者：
Baber R