Index coding via linear programming
Index coding via linear programming
复制标题
DOI：
--
复制
发表时间：
2010-04
期刊：
影响因子：
--
通讯作者：
A. Błasiak;Robert D. Kleinberg;E. Lubetzky
中科院分区：
文献类型：
--
作者：
A. Błasiak;Robert D. Kleinberg;E. Lubetzky
索引编码最近受到了现实应用程序的一部分引起的关注，部分原因是它与网络编码有关。索引编码的基本设置将问题输入编码为无向图，而基本参数是广播率$ \ beta $，对于足够长的消息（即非线性矢量容量），平均每位通信成本。 Bar-Yossef等人（2006），Lubetzky和Stav（2007）和Alon等（2008年）。但是，这些间接界限几乎没有阐明$ \ beta $的行为：在一般网络中近似于$ \ beta $的行为，在非平地内（即$ o（n）$）因素，$ \ beta $， $ \ beta $的确切值对于任何索引编码都不容易的图表仍然不明。我们的主要贡献是使用线性程序对广播率$ \ beta $进行直接信息理论分析，与以前的方法相比，将$ \ beta $与图形理论参数进行了对比。这使我们能够解决上述两个开放问题。我们提供了多项式时间算法，具有在通用网络中计算$ \ beta $以及多项式时间决策程序的非平地近似比，用于识别$ \ beta = 2 $的实例。此外，我们精确地查明了针对各种图形（例如，对于环状组的各种Cayley图）的$ \ beta $，从而同时改善了这些图形的先前已知的上限和下限。通过这种方法，我们构造图形，其中$ \ beta $及其微不足道的下限之间的差异是在顶点的数量和$ \ beta $均匀界限的顶点的线性，而其上限是从幼稚编码方案得出的上限，在多个方面更糟。
Index Coding has received considerable attention recently motivated in part by real-world applications and in part by its connection to Network Coding. The basic setting of Index Coding encodes the problem input as an undirected graph and the fundamental parameter is the broadcast rate $\beta$, the average communication cost per bit for sufficiently long messages (i.e. the non-linear vector capacity). Recent nontrivial bounds on $\beta$ were derived from the study of other Index Coding capacities (e.g. the scalar capacity $\beta_1$) by Bar-Yossef et al (2006), Lubetzky and Stav (2007) and Alon et al (2008). However, these indirect bounds shed little light on the behavior of $\beta$: there was no known polynomial-time algorithm for approximating $\beta$ in a general network to within a nontrivial (i.e. $o(n)$) factor, and the exact value of $\beta$ remained unknown for any graph where Index Coding is nontrivial. Our main contribution is a direct information-theoretic analysis of the broadcast rate $\beta$ using linear programs, in contrast to previous approaches that compared $\beta$ with graph-theoretic parameters. This allows us to resolve the aforementioned two open questions. We provide a polynomial-time algorithm with a nontrivial approximation ratio for computing $\beta$ in a general network along with a polynomial-time decision procedure for recognizing instances with $\beta=2$. In addition, we pinpoint $\beta$ precisely for various classes of graphs (e.g. for various Cayley graphs of cyclic groups) thereby simultaneously improving the previously known upper and lower bounds for these graphs. Via this approach we construct graphs where the difference between $\beta$ and its trivial lower bound is linear in the number of vertices and ones where $\beta$ is uniformly bounded while its upper bound derived from the naive encoding scheme is polynomially worse.