Lower Bounds for Total Storage of Multiset Combinatorial Batch Codes Using Linear Programming
Yeow Meng Chee, Han Mao Kiah, Hui Zhang · IEEE Transactions on Information Theory · 2020
The class of multiset combinatorial batch codes (MCBCs) was introduced by Zhang et al. (2018) as a generalization of combinatorial batch codes (CBCs), which are replication-based batch codes. The MCBCs allow multiple users to retrieve items in parallel in a distributed storage and a fundamental objective in this study is to determine the minimum total storage given certain requirements. We formulate linear programs so that the optimal solutions provide lower bounds on the total storage of MCBCs. Borrowing techniques from linear programming, we improve known lower bounds in some cases. Furthermore, for some parameters, we showed that these lower bounds are either tight or asymptotically tight by constructing the corresponding codes.