Combinatorial batch codes and transversal matroids. (English) Zbl 1290.05048

Brualdi, Richard A.; Kiernan, Kathleen P.; Meyer, Seth A.; Schroeder, Michael W.

Adv. Math. Commun. 4, No. 3, 419-431 (2010).

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\).

MSC:

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

Keywords:

combinatorial batch codes; transversal matroid; dual matroid; cocircuit; presentation of a transversal matroid