-
Abstract
Combinatorial batch codes were defined by Paterson, Stinson, and
Wei as purely combinatorial versions of the batch codes introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai. There are $n$ items and $m$ servers each of which stores a subset of the items. It is required that, for prescribed integers $k$ and $t$, any $k$ items can be retrieved by reading at most $t$ items from each server. Only the case $t=1$ is considered here. An optimal combinatorial batch code is one in which the total storage required is a minimum. We establish an important connection between combinatorial batch codes and transversal matroids, and exploit this connection to characterize optimal combinatorial batch codes if $n=m+1$ and $n=m+2$.
Mathematics Subject Classification: Primary: 05B30, 05B35, 05D05, 68P20, 68R05.
\begin{equation} \\ \end{equation}
-
Access History
-