Index coding, or broadcasting with side information, is a network coding problem of most fundamental importance. In this problem, given a directed graph, each vertex represents a user with a need of information, and the neighborhood of each vertex represents the side information availability to that user. The aim is to find an encoding to minimum number of bits (optimal rate) that, when broadcasted, will be sufficient to the need of every user. Not only the optimal rate is intractable, but it is also very hard to characterize with some other well-studied graph parameter or with a simpler formulation, such as a linear program. Recently there have been a series of works that address this question and provide explicit schemes for index coding as the optimal value of a linear program with rate given by well-studied properties such as local chromatic number or partial clique-covering number. There has been a recent attempt to combine these existing notions of local chromatic number and partial clique covering into a unified notion denoted as the local partial clique cover (Arbabjolfaei and Kim, 2014). We present a generalized novel upper-bound (encoding scheme) - in the form of the minimum value of a linear program - for optimal index coding. Our bound also combines the notions of local chromatic number and partial clique covering into a new definition of the local partial clique cover, which outperforms both the previous bounds, as well as beats the previous attempt to combination.
|Original language||English (US)|
|Title of host publication||2016 International Conference on Signal Processing and Communications, SPCOM 2016|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|State||Published - Nov 16 2016|
|Event||11th International Conference on Signal Processing and Communications, SPCOM 2016 - Bangalore, India|
Duration: Jun 12 2016 → Jun 15 2016
|Name||2016 International Conference on Signal Processing and Communications, SPCOM 2016|
|Other||11th International Conference on Signal Processing and Communications, SPCOM 2016|
|Period||6/12/16 → 6/15/16|
Bibliographical noteFunding Information:
Research supported by NSF grants CCF 1318093 and CAREER CCF 1453121.
© 2016 IEEE.