On the Complementary Index Coding Problem
The index coding problem is one of the basic problems in wireless network coding. In this problem, a server needs to deliver a set P of packets to several clients through a noiseless broadcast channel. Each client needs to obtain a certain subset of P and has prior side information about a different subset of P. The objective is to satisfy the requirements of all clients with the minimum number of transmissions. Recently, it was shown that the index coding problem is NP-hard. Furthermore, this problem was shown to be hard to approximate under a widely accepted complexity assumption.