Optimal combinatorial batch codes derived from dual systems
Csilla Bujtás, Źsolt Tuza · Miskolc mathematical notes/Mathematical notes · 2011
Combinatorial batch codes with parameters n, k, m, and t D 1 may be viewed as set systems F consisting of n subsets over an m-element set (repetitions allowed), satisfying the following restricted version of Hall's Condition: for every 1 Ä i Ä k, the union of any i members of F has cardinality at least i.An optimization problem is to determine N.n; k; m/, the minimum total size P F 2F jF j in such systems.Beside its theoretical interest, the problem has strong practical motivation, too, concerning distributed storage and retrieval of data in a database.Already the case n D m C 2 turns out to be somewhat complicated.Here we give explicit optimal constructions and prove the following formulae: in the range k Ä m Ä k C p k N.m C 2; k; m/ D 2m C k m k C 1 ;and if m > k C p k thenOur method is purely combinatorial, whereas the first proof by Brualdi et al.[Adv.Math.Commun., 4 (2010), 419-431 & 597] used the theory of transversal matroids.We also present an optimality-preserving transformation, by which a large family of non-isomorphic optimal constructions can be derived if one is already available.Moreover, we prove a new general upper bound on N.n; k; m/.