论文标题
集体广播索引编码问题的独立用户分区多播计划
Independent User Partition Multicast Scheme for the Groupcast Index Coding Problem
论文作者
论文摘要
GroupCast索引编码（GIC）问题是索引编码问题的概括，其中一个数据包可以由多个用户要求。在本文中，我们为GIC问题提出了一种新的编码方案，称为独立用户分区元播（IUPM）。与用户分区多播（UPM）（Shanmugam \ textit {et al。}，2015年）相比，该方案的新颖性是通过消除线性依赖的编码数据包来删除UPM解决方案中的冗余。我们还证明，UPM方案包含数据包分区多播（PPM）方案（Tehrani \ textit {et al。}，2012年）。因此，IUPM方案是PPM和UPM方案的概括。此外，受到共同考虑用户和数据包的启发，我们修改了近似分区多播（CAPM）方案（Unal and Wagner，2016），以实现一种新的多项式时间算法来解决一般的GIC问题。我们用$ \ frac {k（k-1）} {2} $数据包来表征一类GIC问题，对于任何整数$ k \ geq 2 $，IUPM方案是最佳的。我们还证明，对于此类，建议的新启发式算法的广播速率为$ K $，而CAPM方案的广播率为$ \ Mathcal {O}（k^2）$。
The groupcast index coding (GIC) problem is a generalization of the index coding problem, where one packet can be demanded by multiple users. In this paper, we propose a new coding scheme called independent user partition multicast (IUPM) for the GIC problem. The novelty of this scheme compared to the user partition multicast (UPM) (Shanmugam \textit{et al.}, 2015) is in removing redundancies in the UPM solution by eliminating the linearly dependent coded packets. We also prove that the UPM scheme subsumes the packet partition multicast (PPM) scheme (Tehrani \textit{et al.}, 2012). Hence, the IUPM scheme is a generalization of both PPM and UPM schemes. Furthermore, inspired by jointly considering users and packets, we modify the approximation partition multicast (CAPM) scheme (Unal and Wagner, 2016) to achieve a new polynomial-time algorithm for solving the general GIC problem. We characterize a class of GIC problems with $\frac{k(k-1)}{2}$ packets, for any integer $k\geq 2$, for which the IUPM scheme is optimal. We also prove that for this class, the broadcast rate of the proposed new heuristic algorithm is $k$, while the broadcast rate of the CAPM scheme is $\mathcal{O}(k^2)$.
