TY - GEN
T1 - A Polynomial-Time Algorithm for Pliable Index Coding
AU - Song, Linqi
AU - Fragouli, Christina
PY - 2016/7
Y1 - 2016/7
N2 - Pliable index coding considers a server with m messages and n clients where each client has as side information a subset of the messages. We seek to minimize the number of transmissions the server should make, so that each client receives (any) one message she does not already have. Previous work has shown that the server can achieve this using at most O(log2(n)) transmissions and needs at least Ω(log(n)) transmissions in the worst case, but finding a code of optimal length is NP-hard. In this paper, we design a polynomial-time algorithm that uses less than O(log2(n)) transmissions, i.e., almost worst-case optimal. We also establish a connection between the pliable index coding problem and the minrank problem over a family of mixed matrices.
AB - Pliable index coding considers a server with m messages and n clients where each client has as side information a subset of the messages. We seek to minimize the number of transmissions the server should make, so that each client receives (any) one message she does not already have. Previous work has shown that the server can achieve this using at most O(log2(n)) transmissions and needs at least Ω(log(n)) transmissions in the worst case, but finding a code of optimal length is NP-hard. In this paper, we design a polynomial-time algorithm that uses less than O(log2(n)) transmissions, i.e., almost worst-case optimal. We also establish a connection between the pliable index coding problem and the minrank problem over a family of mixed matrices.
UR - http://www.scopus.com/inward/record.url?scp=84985998199&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84985998199&origin=recordpage
U2 - 10.1109/ISIT.2016.7541273
DO - 10.1109/ISIT.2016.7541273
M3 - 32_Refereed conference paper (with host publication)
SN - 9781509018079
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 120
EP - 124
BT - Proceedings 2016 IEEE International Symposium on Information Theory (ISIT 2016)
PB - IEEE
T2 - 2016 IEEE International Symposium on Information Theory (ISIT 2016)
Y2 - 10 July 2016 through 15 July 2016
ER -