@article {IOPORT.05990741,
    author       = {Bujt\'as, Csilla and Tuza, Zsolt},
    title        = {Optimal combinatorial batch codes derived from dual systems.},
    year         = {2011},
    journal      = {Mathematical Notes (Miskolc)},
    volume       = {12},
    number       = {1},
    issn         = {1586-8850},
    pages        = {11-23},
    publisher    = {Miskolc University Press, Miskolc},
    abstract     = {Summary: Combinatorial batch codes with parameters $n$, $k$, $m$, and $t=1$ may be viewed as set systems $\Cal F$ consisting of $n$ subsets over an $m$-element set (repetitions allowed), satisfying the following restricted version of Hall's Condition: for every $1\le i\le k$, the union of any $i$ members of $\Cal F$ has cardinality at least $i$ . An optimization problem is to determine $N(n,k,m)$, the minimum total size $\sum_{F\in \Cal F}\vert F\vert $ 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= m+ 2$ turns out to be somewhat complicated. Here we give explicit optimal constructions and prove the following formulae: in the range $k\le m\le k +\sqrt k$ $$ N(m+2,k,m)= 2m+\left\lfloor\frac{k}{m-k+1}\right\rfloor, $$ and if $m +\sqrt k$ then $$ N(m+2,k,m)= N(m+1,k,m-1)+1= m+ k-2\left\lceil 2\sqrt{k+1}\right\rceil $$ for all $m \ge k\ge 1$. Our method is purely combinatorial, whereas the first proof by {\it R. A. Brualdi, K. P. Kiernan, S. A. Meyer, M. W. Schroeder} [Adv. Math. Commun., 4, 419--431 (2010; Zbl Zbl 05903540)] 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)$.},
    identifier   = {05990741},
}