TY - JOUR
T1 - A Polynomial-Time Algorithm for Pliable Index Coding
AU - Song, Linqi
AU - Fragouli, Christina
PY - 2018/2
Y1 - 2018/2
N2 - In pliable index coding, we consider 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 broadcast transmissions, so that each client can recover any one unknown message she does not already have. Previous work has shown that the pliable index coding problem is NP-hard and requires at most O(log2(n)) broadcast transmissions, which indicates exponential savings over the conventional index coding that requires in the worst case O(n) transmissions. In this paper, building on a decoding criterion that we propose, we first design a deterministic polynomial-time algorithm that can realize the exponential benefits, by achieving, in the worst case, a performance upper bounded by O(log2(n)) broadcast transmissions. We extend our algorithm to the t-requests case, where each client requires t unknown messages that she does not have, and show that our algorithm requires at most O(t log(n) + log2(n)) broadcast transmissions. We construct lower bound instances that require at least Ω (log(n)) transmissions for linear pliable index coding and at least Ω (t + log(n)) transmissions for the t-requests case, indicating that both our upper and lower bounds are polynomials of log(n) and differ within a factor of O(log(n)). We provide a probabilistic analysis over random instances and show that the required number of transmissions is almost surely Θ (log(n)) , as compared with the Θ (n/log(n)) for index coding. In addition, we show that these upper and lower bounds also hold for vector pliable index coding in the worst case instances and the random graph instances, implying that vector coding does not provide benefits in terms of these bounds. Our numerical experiments show that our algorithm outperforms existing algorithms for pliable index coding by up to 50% less transmissions.
AB - In pliable index coding, we consider 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 broadcast transmissions, so that each client can recover any one unknown message she does not already have. Previous work has shown that the pliable index coding problem is NP-hard and requires at most O(log2(n)) broadcast transmissions, which indicates exponential savings over the conventional index coding that requires in the worst case O(n) transmissions. In this paper, building on a decoding criterion that we propose, we first design a deterministic polynomial-time algorithm that can realize the exponential benefits, by achieving, in the worst case, a performance upper bounded by O(log2(n)) broadcast transmissions. We extend our algorithm to the t-requests case, where each client requires t unknown messages that she does not have, and show that our algorithm requires at most O(t log(n) + log2(n)) broadcast transmissions. We construct lower bound instances that require at least Ω (log(n)) transmissions for linear pliable index coding and at least Ω (t + log(n)) transmissions for the t-requests case, indicating that both our upper and lower bounds are polynomials of log(n) and differ within a factor of O(log(n)). We provide a probabilistic analysis over random instances and show that the required number of transmissions is almost surely Θ (log(n)) , as compared with the Θ (n/log(n)) for index coding. In addition, we show that these upper and lower bounds also hold for vector pliable index coding in the worst case instances and the random graph instances, implying that vector coding does not provide benefits in terms of these bounds. Our numerical experiments show that our algorithm outperforms existing algorithms for pliable index coding by up to 50% less transmissions.
KW - greedy algorithm
KW - index coding
KW - Pliable index coding
KW - Polynomial time algorithm
KW - random graphs
KW - t-requests
UR - http://www.scopus.com/inward/record.url?scp=85030246180&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85030246180&origin=recordpage
U2 - 10.1109/TIT.2017.2752088
DO - 10.1109/TIT.2017.2752088
M3 - RGC 21 - Publication in refereed journal
VL - 64
SP - 979
EP - 999
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
SN - 0018-9448
IS - 2
M1 - 8036234
ER -