The results on optimal values of some combinatorial batch codes
Yuebo Shen, Dongdong Jia, Gengsheng Zhang · Advances in Mathematics of Communications · 2018
An $(n,N,k,m)$-combinatorial batch code (CBC) was defined by Paterson, Stinson and Wei as a purely combinatorial version of batch codes which were first proposed by Ishai, Kushilevitz, Ostrovsky and Sahai. It is a system consisting of $m$ subsets of an $n$-element set such that any $k$ distinct 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 goal is to determine the minimum $N$, denoted by $N(n,k,m)$.So far, for $k≥5$, $m+3≤ n< \binom{m}{k-2}$, precise values of $N(n,k,m)$ have not been established except for some special parameters. In this paper, we present a lower bound on $N(n,k,k+1)$, which is tight for some $n$ and $k$. Based on this lower bound, the monotonicity of optimal values of CBC and several constructions, we obtain $N(m+4,5,m)$, $N(m+4,6,m)$ and $N(m+3,7,m)$ in different ways.