Lower Bounds for Total Storage of Multiset Combinatorial Batch Codes Using Linear Programming
- 8 October 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (1) , 255-267
Abstract
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.Keywords
Funding Information
- National Research Foundation, Singapore, through its Strategic Capability Research Centres Funding Initiative
- National Research Foundation, Singapore (NRF-RSS2016-004)
This publication has 27 references indexed in Scilit:
- Optimal Fractional Repetition Codes Based on Graphs and DesignsIEEE Transactions on Information Theory, 2015
- Turán numbers and batch codesDiscrete Applied Mathematics, 2015
- Fractional Repetition and Erasure Batch Codes2015
- Optimal combinatorial batch codes based on block designsDesigns, Codes and Cryptography, 2014
- On an extremal hypergraph problem related to combinatorial batch codesDiscrete Applied Mathematics, 2014
- Combinatorial batch codes: A lower bound and optimal constructionsAdvances in Mathematics of Communications, 2012
- Relaxations of Hall’s Condition: Optimal batch codes with multiple queriesApplicable Analysis and Discrete Mathematics, 2012
- Optimal batch codes: Many items or low retrieval requirementAdvances in Mathematics of Communications, 2011
- Combinatorial batch codes and transversal matroidsAdvances in Mathematics of Communications, 2010
- Combinatorial batch codesAdvances in Mathematics of Communications, 2009