Finding Sparse Solutions for the Index Coding Problem

Abstract

The Index Coding problem has recently attracted a significant attention from the research community. In this problem, a server needs to deliver data to a set of wireless clients over the broadcast channel. Each client requires one or more packets, but it might have access to the packets requested by other clients as side information. The goal is to deliver the required data to each client with minimum number of transmissions. In this paper, we focus on finding sparse solutions to the Index Coding problem. In a sparse solution each transmitted packet is a linear combination of at most two original packets. We focus both on scalar and vector versions of the problem. For the scalar case, we present a polynomial time algorithm that achieves an approximation ratio of 2-(1/√n). For the vector case, we present a polynomial time algorithm that identifies an optimal solution to the problem. Our simulation studies demonstrate that our algorithms achieve good performance in practical scenarios.