zbMATH — the first resource for mathematics

Combinatorial batch codes and transversal matroids. (English) Zbl 1290.05048
Summary: Combinatorial batch codes were defined by Paterson, Stinson, and Wei as purely combinatorial versions of the batch codes introduced by Y. Ishai et al. [in: Proceedings of the 36th annual ACM symposium on theory of computing, STOC 2004. New York, NY: ACM Press. 262–271 (2004; Zbl 1192.94100)]. 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\).

05B30 Other designs, configurations
05B35 Combinatorial aspects of matroids and geometric lattices
05D05 Extremal set theory
68P20 Information storage and retrieval of data
68R05 Combinatorics in computer science
94A60 Cryptography
94B60 Other types of codes
Full Text: DOI