Local Partial Clique and Cycle Covers for Index Coding

摘要

We present a generalized novel upper-bound (and encoding scheme) - in the form of the minimum value of a linear program - for optimal index coding. Our scheme combines the notions of local chromatic number and partial clique covering into a new definition of the local partial clique cover, which outperforms the previous bounds such as the one by Arbabjolfaei and Kim, 2014. Further, we look at the upper bound derived recently by Thapa et al., 2015, and extend their n-GIC (Generalized Interlinked Cycle) construction to (k,n)GIC graphs, which are a generalization of k-partial cliques.