Efficient Algorithms for Index Coding

The Index Coding problem has attracted a considerable amount of attention in recent years. The problem is motivated by several applications in wireless networking and distributed computing, including wireless network architectures that utilize network coding and opportunistic listening. In this poster, we propose efficient exact and heuristic solutions for the Index Coding problem. While Index Coding is hard to approximate, we also consider the complimentary problem to Index Coding problem, the goal of the complimentary problem is to "maximize the number of saved transmissions". We present two approximate algorithms to the complimentary problem. Our numerical study suggests that the exact solutions can be efficiently identified for small instances, while the approximate and heuristic solutions with low computation time can achieve near-optimal performance for larger instances.

day4_Mohammad Asad Chaudhry_Index Coding..pdf — PDF document, 465Kb