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. 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.

show all references

References:
[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.

[1]

Changlu Liu, Shuangli Qiao. Symmetry and monotonicity for a system of integral equations. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1925-1932. doi: 10.3934/cpaa.2009.8.1925

[2]

Yulin Zhao. On the monotonicity of the period function of a quadratic system. Discrete & Continuous Dynamical Systems - A, 2005, 13 (3) : 795-810. doi: 10.3934/dcds.2005.13.795

[3]

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 & Management Optimization, 2018, 14 (2) : 473-496. doi: 10.3934/jimo.2017056

[4]

Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Distributed optimal control of a nonstandard nonlocal phase field system with double obstacle potential. Evolution Equations & Control Theory, 2017, 6 (1) : 35-58. doi: 10.3934/eect.2017003

[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 & Games, 2016, 3 (4) : 371-398. doi: 10.3934/jdg.2016020

[7]

Sze-Bi Hsu, Junping Shi, Feng-Bin Wang. Further studies of a reaction-diffusion system for an unstirred chemostat with internal storage. Discrete & Continuous Dynamical Systems - B, 2014, 19 (10) : 3169-3189. doi: 10.3934/dcdsb.2014.19.3169

[8]

Chin-Chin Wu. Monotonicity and uniqueness of wave profiles for a three components lattice dynamical system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (5) : 2813-2827. doi: 10.3934/dcds.2017121

[9]

Getachew K. Befekadu, Eduardo L. Pasiliao. On the hierarchical optimal control of a chain of distributed systems. Journal of Dynamics & Games, 2015, 2 (2) : 187-199. doi: 10.3934/jdg.2015.2.187

[10]

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

[11]

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

[12]

Shunfu Jin, Yuan Zhao, Wuyi Yue, Lingling Chen. Performance analysis of a P2P storage system with a lazy replica repair policy. Journal of Industrial & Management Optimization, 2014, 10 (1) : 151-166. doi: 10.3934/jimo.2014.10.151

[13]

Zhaoquan Xu, Jiying Ma. Monotonicity, asymptotics and uniqueness of travelling wave solution of a non-local delayed lattice dynamical system. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 5107-5131. doi: 10.3934/dcds.2015.35.5107

[14]

Zhenguo Bai, Tingting Zhao. Spreading speed and traveling waves for a non-local delayed reaction-diffusion system without quasi-monotonicity. Discrete & Continuous Dynamical Systems - B, 2018, 23 (10) : 4063-4085. doi: 10.3934/dcdsb.2018126

[15]

Samuel Bernard, Fabien Crauste. Optimal linear stability condition for scalar differential equations with distributed delay. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 1855-1876. doi: 10.3934/dcdsb.2015.20.1855

[16]

Shin-Guang Chen. Optimal double-resource assignment for a distributed multistate network. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1375-1391. doi: 10.3934/jimo.2015.11.1375

[17]

Hongming Yang, Dexin Yi, Junhua Zhao, Fengji Luo, Zhaoyang Dong. Distributed optimal dispatch of virtual power plant based on ELM transformation. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1297-1318. doi: 10.3934/jimo.2014.10.1297

[18]

Giulio Caravagna, Alex Graudenzi, Alberto d’Onofrio. Distributed delays in a hybrid model of tumor-Immune system interplay. Mathematical Biosciences & Engineering, 2013, 10 (1) : 37-57. doi: 10.3934/mbe.2013.10.37

[19]

Canan Çelik. Dynamical behavior of a ratio dependent predator-prey system with distributed delay. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 719-738. doi: 10.3934/dcdsb.2011.16.719

[20]

Fuke Wu, Yangzi Hu. Stochastic Lotka-Volterra system with unbounded distributed delay. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 275-288. doi: 10.3934/dcdsb.2010.14.275

2017 Impact Factor: 0.564

Article outline

[Back to Top]