  Combinatorial Batch Codes (CBCs), replication-based variant of Batch Codes
introduced by Ishai et al. in STOC 2004, abstracts the following data
distribution problem: $n$ data items are to be replicated among $m$ servers in
such a way that any $k$ of the $n$ data items can be retrieved by reading at
most one item from each server with the total amount of storage over $m$
servers restricted to $N$. Given parameters $m, c,$ and $k$, where $c$ and $k$
are constants, one of the challenging problems is to construct $c$-uniform CBCs
(CBCs where each data item is replicated among exactly $c$ servers) which
maximizes the value of $n$. In this work, we present explicit construction of
$c$-uniform CBCs with $\Omega(m^{c-1+{1 \over k}})$ data items. The
construction has the property that the servers are almost regular, i.e., number
of data items stored in each server is in the range $[{nc \over
m}-\sqrt{{n\over 2}\ln (4m)}, {nc \over m}+\sqrt{{n \over 2}\ln (4m)}]$. The
construction is obtained through better analysis and derandomization of the
randomized construction presented by Ishai et al. Analysis reveals almost
regularity of the servers, an aspect that so far has not been addressed in the
literature. The derandomization leads to explicit construction for a wide range
of values of $c$ (for given $m$ and $k$) where no other explicit construction
with similar parameters, i.e., with $n = \Omega(m^{c-1+{1 \over k}})$, is
known. Finally, we discuss possibility of parallel derandomization of the
construction.
