A Class Of Optimal Combinatorial Batch Code

Batch codes were first proposed by Ishai, Kushilevitz, Ostrovsky and Sahai in 2004. An (n, N, k, m)-combinatorial batch code was defined by Peterson et al. in 2009, as a purely combinatorial version of batch codes. It is a system consisting of m subsets of an n-element set such that any k elements can be retrieved by reading at most one(or in general, t) elements from each subset and the number of total elements in m subsets is N. For given parameters n, k, m, the minimum N, denoted by N(n, k, m), is of particular interest, which has both theoretical interests in combinatorial mathematics and strong practical value in computer information storage.So far, for k≥5,m+3≤n< (k-2 m), precise values of N(n,k,m) have not been established except for some special settings of the parameters. In this paper, we first present some preliminaries of combinatorial batch codes in Chapter 1. In the rest of paper, we obtain following optimal values of CBCs in different ways:N(m+3,5,m)=m+11(m≥7), N(9,5,6)=18.N(m+3,6, m)= m+13(m≥8), N(10,6,7)= 21.N(m+4,5,m)= m+13(m≥8), N(m+4,5,m)= 21 (m= 6,7).N(m+4,6,m)=m+16(m≥8), N(11,6,7)= 25.We also give explicit constructions of optimal CBCs with corresponding parameters. Our results partly answer an open problem of Paterson et al.