Advances in Mathematics of Communications (AMC)

 Combinatorial batch codes: A lower bound and optimal constructions Pages: 165 - 174, Volume 6, Issue 2, May 2012 Srimanta Bhattacharya - Applied Statistics Unit, Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India (email) Sushmita Ruj - School of Information Technology and Engineering, University of Ottawa, Ottawa, K1N6N5, Canada (email) Bimal Roy - Applied Statistics Unit, Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India (email) Abstract: Batch codes, introduced by Ishai et al. in [11], are methods for solving the following data storage problem: $n$ data items are to be stored in $m$ servers in such a way that any $k$ of the $n$ items can be retrieved by reading at most $t$ items from each server, and that the total number of items stored in $m$ servers is $N$. A combinatorial batch code (CBC) is a batch code where each data item is stored without change, i.e., each stored data item is a copy of one of the $n$ data items.     One of the basic yet challenging problems is to find optimal CBCs, i.e., CBCs for which total storage ($N$) is minimal for given values of $n$, $m$, $k$, and $t$. In [13], Paterson et al. exclusively studied CBCs and gave constructions of some optimal CBCs.     In this article, we give a lower bound on the total storage ($N$) for CBCs. We give explicit construction of optimal CBCs for a range of values of $n$. For a different range of values of $n$, we give explicit construction of optimal and almost optimal CBCs. Our results partly settle an open problem of [13]. Keywords:  Combinatorial batch codes, Hall's theorem, binary constant weight codes. Mathematics Subject Classification:  Primary: 05D05, 68P30; Secondary: 68P20. Received: February 2011;      Revised: December 2011;      Published: April 2012.  References 2011 Impact Factor.462