# American Institute of Mathematical Sciences

November  2018, 12(4): 681-690. doi: 10.3934/amc.2018040

## The results on optimal values of some combinatorial batch codes

 1 Information Department, Children's Hospital of Hebei Province, Shijiazhuang 050031, China 2 College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang 050024, China

* Corresponding author: Gengsheng Zhang

Received  May 2017 Revised  March 2018 Published  September 2018

Fund Project: 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).

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.

Citation: Yuebo Shen, Dongdong Jia, Gengsheng Zhang. The results on optimal values of some combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (4) : 681-690. doi: 10.3934/amc.2018040
##### References:
 [1] S. Bhattacharya, S. 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. Brualdi, K. P. Kiernan, S. 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. Brualdi, K. P. Kiernan, S. 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. Paterson, D. 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.

show all references

##### References:
 [1] S. Bhattacharya, S. 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. Brualdi, K. P. Kiernan, S. 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. Brualdi, K. P. Kiernan, S. 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. Paterson, D. 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.
 [1] Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024 [2] Bosheng Chen, Huilai Li, Changchun Liu. Optimal distributed control for a coupled phase-field system. Discrete and Continuous Dynamical Systems - B, 2022, 27 (3) : 1789-1825. doi: 10.3934/dcdsb.2021110 [3] Changlu Liu, Shuangli Qiao. Symmetry and monotonicity for a system of integral equations. Communications on Pure and Applied Analysis, 2009, 8 (6) : 1925-1932. doi: 10.3934/cpaa.2009.8.1925 [4] Yulin Zhao. On the monotonicity of the period function of a quadratic system. Discrete and Continuous Dynamical Systems, 2005, 13 (3) : 795-810. doi: 10.3934/dcds.2005.13.795 [5] Gokhan Calis, O. Ozan Koyluoglu. Architecture-aware coding for distributed storage: Repairable block failure resilient codes. Advances in Mathematics of Communications, 2018, 12 (3) : 465-503. doi: 10.3934/amc.2018028 [6] Lisa C Flatley, Robert S MacKay, Michael Waterson. Optimal strategies for operating energy storage in an arbitrage or smoothing market. Journal of Dynamics and Games, 2016, 3 (4) : 371-398. doi: 10.3934/jdg.2016020 [7] Kareem T. Elgindy. Optimal control of a parabolic distributed parameter system using a fully exponentially convergent barycentric shifted gegenbauer integral pseudospectral method. Journal of Industrial and Management Optimization, 2018, 14 (2) : 473-496. doi: 10.3934/jimo.2017056 [8] Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Distributed optimal control of a nonstandard nonlocal phase field system with double obstacle potential. Evolution Equations and Control Theory, 2017, 6 (1) : 35-58. doi: 10.3934/eect.2017003 [9] Sze-Bi Hsu, Junping Shi, Feng-Bin Wang. Further studies of a reaction-diffusion system for an unstirred chemostat with internal storage. Discrete and Continuous Dynamical Systems - B, 2014, 19 (10) : 3169-3189. doi: 10.3934/dcdsb.2014.19.3169 [10] Hua Nie, Sze-Bi Hsu, Feng-Bin Wang. Global dynamics of a reaction-diffusion system with intraguild predation and internal storage. Discrete and Continuous Dynamical Systems - B, 2020, 25 (3) : 877-901. doi: 10.3934/dcdsb.2019194 [11] Getachew K. Befekadu, Eduardo L. Pasiliao. On the hierarchical optimal control of a chain of distributed systems. Journal of Dynamics and Games, 2015, 2 (2) : 187-199. doi: 10.3934/jdg.2015.2.187 [12] Chin-Chin Wu. Monotonicity and uniqueness of wave profiles for a three components lattice dynamical system. Discrete and Continuous Dynamical Systems, 2017, 37 (5) : 2813-2827. doi: 10.3934/dcds.2017121 [13] Shunfu Jin, Yuan Zhao, Wuyi Yue, Lingling Chen. Performance analysis of a P2P storage system with a lazy replica repair policy. Journal of Industrial and Management Optimization, 2014, 10 (1) : 151-166. doi: 10.3934/jimo.2014.10.151 [14] Andrey Yu. Verisokin, Darya V. Verveyko, Eugene B. Postnikov, Anastasia I. Lavrova. Wavelet analysis of phase clusters in a distributed biochemical system. Conference Publications, 2011, 2011 (Special) : 1404-1412. doi: 10.3934/proc.2011.2011.1404 [15] Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052 [16] Domingo Tarzia, Carolina Bollo, Claudia Gariboldi. Convergence of simultaneous distributed-boundary parabolic optimal control problems. Evolution Equations and Control Theory, 2020, 9 (4) : 1187-1201. doi: 10.3934/eect.2020045 [17] Samuel Bernard, Fabien Crauste. Optimal linear stability condition for scalar differential equations with distributed delay. Discrete and Continuous Dynamical Systems - B, 2015, 20 (7) : 1855-1876. doi: 10.3934/dcdsb.2015.20.1855 [18] Shin-Guang Chen. Optimal double-resource assignment for a distributed multistate network. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1375-1391. doi: 10.3934/jimo.2015.11.1375 [19] Hongming Yang, Dexin Yi, Junhua Zhao, Fengji Luo, Zhaoyang Dong. Distributed optimal dispatch of virtual power plant based on ELM transformation. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1297-1318. doi: 10.3934/jimo.2014.10.1297 [20] Nguyen Hai Son. Solution stability to parametric distributed optimal control problems with finite unilateral constraints. Evolution Equations and Control Theory, 2021  doi: 10.3934/eect.2021047

2020 Impact Factor: 0.935