A Lower Bound on Load of Coded Caching Schemes for Finite Subpacketizations
Minquan Cheng, Youlong Wu · 2022
Coded caching is a technique to create coded multicast opportunities for cache-aided networks. In coded caching problem, a fundamental but open question is: what is the minimum transmission load given any fixed subpacketization level? In this paper, we propose a lower bound on the transmission load for any fixed subpacketization by studying the combinatorial structure of corresponding placement delivery array, which was introduced by Yan et al. to reformulate the centralized coded caching schemes. Then we show that some schemes generated by the well known scheme proposed by Maddah-Ali and Niesen (MN), and some scheme generated by Packing (a classic concept of combinatorial design theory), can achieve our lower bound. This implies that our lower bound is tight for some cases.