Advanced Search
Article Contents
Article Contents

Combinatorial batch codes and transversal matroids

Abstract Related Papers Cited by
  • 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}
  • 加载中

Article Metrics

HTML views() PDF downloads(111) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint