Date Added: Apr 2013
The authors consider the scenario of broadcasting for real-time applications and loss recovery via instantly decodable network coding. Past work focused on minimizing the completion delay, which is not the right objective for real-time applications that have strict deadlines. In this paper, they are interested in finding a code that is instantly decodable by the maximum number of users. First, they prove that this problem is NP-Hard in the general case. Then they consider the practical probabilistic scenario, where users have the i.i.d. loss probability and the number of packets is linear or polynomial in the number of users, and they provide a polynomial-time (in the number of users) algorithm that finds the optimal coded packet.