Advanced Search
Article Contents
Article Contents

The results on optimal values of some combinatorial batch codes

  • * Corresponding author: Gengsheng Zhang

    * Corresponding author: Gengsheng Zhang
This research is partially supported by National Natural Science Foundation of China (Grant No. 11571091), Natural Science Foundation of Hebei Education Department (Grant No. ZD2016096) and Research Project of Health Commission of Hebei Province (Grant No. 20160419)
Abstract Full Text(HTML) Related Papers Cited by
  • An $(n,N,k,m)$-combinatorial batch code (CBC) was defined by Paterson, Stinson and Wei as a purely combinatorial version of batch codes which were first proposed by Ishai, Kushilevitz, Ostrovsky and Sahai. It is a system consisting of $m$ subsets of an $n$-element set such that any $k$ distinct elements can be retrieved by reading at most one (or in general, $t$) elements from each subset and the number of total elements in $m$ subsets is $N$. For given parameters $n,k,m$, the goal is to determine the minimum $N$, denoted by $N(n,k,m)$.

    So far, for $k≥5$, $m+3≤ n< \binom{m}{k-2}$, precise values of $N(n,k,m)$ have not been established except for some special parameters. In this paper, we present a lower bound on $N(n,k,k+1)$, which is tight for some $n$ and $k$. Based on this lower bound, the monotonicity of optimal values of CBC and several constructions, we obtain $N(m+4,5,m)$, $N(m+4,6,m)$ and $N(m+3,7,m)$ in different ways.

    Mathematics Subject Classification: Primary: 05B30, 05D05; Secondary: 68P20, 68P30.


    \begin{equation} \\ \end{equation}
  • 加载中
  • [1] S. BhattacharyaS. Ruj and B. Roy, Combinatorial batch codes: A lower bound and optimal constructions, Adv. Math. Commun., 6 (2012), 165-174.  doi: 10.3934/amc.2012.6.165.
    [2] R. A. BrualdiK. P. KiernanS. A. Meyer and M. W. Schroeder, Combinatorial batch codes and transversal matroids, Adv. Math. Commun., 4 (2010), 419-431.  doi: 10.3934/amc.2010.4.419.
    [3] R. A. BrualdiK. P. KiernanS. A. Meyer and M. W. Schroeder, Erratum to " combinatorial batch codes and transversal matroids", Adv. Math. Commun., 4 (2010), 597.  doi: 10.3934/amc.2010.4.597.
    [4] C. Bujtás and Z. Tuza, Optimal batch codes: Many items or low retrieval requirement, Adv. Math. Commun., 5 (2011), 529-541.  doi: 10.3934/amc.2011.5.529.
    [5] C. Bujtás and Z. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes, 12 (2011), 11-23.  doi: 10.18514/MMN.2011.325.
    [6] J. Chen, S. Zhang and G. Zhang, Optimal combinatorial batch code: Monotonicity, lower and upper bounds, Sci. Sin. Math., 45 (2015), 311–320 (in Chinese). doi: 10.1360/N012014-00061.
    [7] Y. Ishai, E. Kushilevitz, R. Ostrovsky and A. Sahai, Batch codes and their applications, in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing STOC' 04, New York, USA, 36 (2004), 262–271. doi: 10.1145/1007352.1007396.
    [8] D. Jia, G. Zhang and L. Yuan, A class of optimal combinatorial batch code, Acta Math. Sinica (Chin. Ser.), 59 (2016), 267–278.(in Chinese)
    [9] M. B. PatersonD. R. Stinson and R. Wei, Combinatorial batch codes, Adv. Math. Commun., 3 (2009), 13-27.  doi: 10.3934/amc.2009.3.13.
    [10] S. Ruj and B. Roy, More on combinatorial batch codes, preprint arXiv: 0809.3357v1.
    [11] N. Silberstein and A. Gál, Optimal combinatorial batch codes based on block designs, Des. Codes Cryptogr., 78 (2016), 409-424.  doi: 10.1007/s10623-014-0007-9.
  • 加载中

Article Metrics

HTML views(713) PDF downloads(425) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint