DocumentCode :
3250762
Title :
Duality codes and the integrality gap bound for index coding
Author :
Hao Yu ; Neely, Michael J.
Author_Institution :
Univ. of Southern California, Los Angeles, CA, USA
fYear :
2013
fDate :
2-4 Oct. 2013
Firstpage :
1553
Lastpage :
1560
Abstract :
This paper considers a base station that delivers packets to multiple receivers through a sequence of coded transmissions. All receivers overhear the same transmissions. Each receiver may already have some of the packets as side information, and requests another subset of the packets. This problem is known as the index coding problem and can be represented by a bipartite digraph. An integer linear program is developed that provides a lower bound on the minimum number of transmissions required for any coding algorithm. Conversely, its linear programming relaxation is shown to provide an upper bound that is achievable by a simple form of vector linear coding. Thus, the information theoretic optimum is bounded by the integrality gap between the integer program and its linear relaxation. In the special case when the digraph has a planar structure, the integrality gap is shown to be zero, so that exact optimality is achieved. Finally, for non-planar problems, an enhanced integer program is constructed that provides a smaller integrality gap. The dual of this problem corresponds to a more sophisticated partial clique coding strategy that time-shares between Reed-Solomon erasure codes. This work illuminates the relationship between index coding, duality, and integrality gaps between integer programs and their linear relaxations.
Keywords :
Reed-Solomon codes; cyclic codes; directed graphs; dual codes; integer programming; linear codes; linear programming; packet radio networks; relaxation theory; Reed-Solomon erasure codes; base station; bipartite digraph; coded transmissions; coding algorithm; duality codes; enhanced integer program; exact optimality; index coding problem; information theoretic optimum; integer linear program; integrality gap; linear programming relaxation; linear relaxation; nonplanar problems; partial clique coding strategy; receivers; vector linear coding; Indexes; Linear codes; Linear programming; Receivers; Unicast; Vectors;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on
Conference_Location :
Monticello, IL
Print_ISBN :
978-1-4799-3409-6
Type :
conf
DOI :
10.1109/Allerton.2013.6736712
Filename :
6736712
Link To Document :
بازگشت