Independent User Partition Multicast Scheme for the Groupcast Index Coding Problem

Abstract

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 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 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 coded 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}}}{2} packets, for any integer k≥ 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}}\left({{k 2}}).