Optimal combinatorial batch code: Monotonicity, lower and upper bounds
SuMei ZHANG, Gengsheng Zhang, JunFang CHEN · Scientia Sinica Mathematica · 2015
A combinatorial batch code with parameters n, k, m is a system consisting of m subsets B1, B2,..., Bm of an n-element set such that any k elements can be retrieved by reading at most one (or in general, t) elements from each subset. An optimization problem is to determine N(n, k, m), the minimum of |B1| + |B2| +··· + |Bm|. This problem has both theoretical interests and strong practical motivation. In this article, we study the fuction N(n, k, m) and give a lower and upper bounds for N(n, k, m): for 2≤k [√k + 1] then (n-m)k + m > N(n, k;m) ≥ 2n-m + k-6 + [2√k + 1; if m + 1-k < [√k + 1] then (n-m)k + m ≥ N(n, k, m)≥2n-6 +[1+(k + 1)/m-k + 1. We also determined that N(m + 3,4,m)=m + 9 (m ≥ 6), N(8, 4, 8)=15. Our results partly settle an open problem of Paterson et al.