一类最优组合批处理码

贾冬冬, 张更生, 袁兰党

数学学报 ›› 2016, Vol. 59 ›› Issue (2) : 267-278.

PDF(602 KB)
PDF(602 KB)
数学学报 ›› 2016, Vol. 59 ›› Issue (2) : 267-278. DOI: 10.12386/A2016sxxb0024
论文

一类最优组合批处理码

    贾冬冬1,2, 张更生1,2, 袁兰党1,2
作者信息 +

A Class of Optimal Combinatorial Batch Code

    Dong Dong JIA1,2, Geng Sheng ZHANG1,2, Lan Dang YUAN1,2
Author information +
文章历史 +

摘要

Ishai 等人首先提出了批处理码的概念, Peterson等人从纯组合的观点定义了 (n,N, k,m)-组合批处理码: 即是一个 n元集和它的 m 个子集组成的集合系统, 对于整数 k, 满足任意 k个元素都 能从每个子集中至多读取 1 个元素(可以一般化为 t个元素)来取得, 此时 m 个子集中元素的总数为 N. 对给定的参数n, k,m, 确定 N 的最小值 N(n, k,m)是该问题研究的中心内容,它不仅具有理论意义, 而且有着重要的使用价值. 到目前为止,除了一些极特殊的参数以外, 当 k ≥ 5, m+3 ≤ n时, N(n, k,m) 的值还没有被确定. 本文给出了N(m+3, 5,m) = m+11 (m ≥ 7), N(9, 5, 6) = 18, N(m+3, 6,m) = m+13 (m ≥ 8), N(10, 6, 7) = 21. 得到的结果部分解决了Peterson等人提出的未解决问题.

Abstract

Batch codes were first proposed by Ishai et al., an (n,N, k,m)-combinatorial batch code was defined by Peterson et al. as a purely combinatorial version of batch codes. It is a system consisting of m subsets 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 and the number of total elements in m subsets is N. For given parameters n, k,m, the minimum N, denoted by N(n, k,m), is of particular interest, which has both theoretical interests and strong practical motivation. So far, for k ≥ 5, m+3 ≤ n <, precise values of N(n, k,m) have not been established except for some special settings of the parameters. In this article, we obtain N(m+3, 5,m) = m+11 (m ≥ 7), N(9, 5, 6) = 18, N(m+3, 6,m) = m+13 (m ≥ 8), N(10, 6, 7) = 21. Our results partly answer an open problem of Paterson et al.

关键词

组合批处理码 / 最优 CBC / 对偶集合系统 / k-限制 Hall条件

Key words

combinatorial batch code / optimal CBC / dual set system / k-restricted Hall condition

引用本文

导出引用
贾冬冬, 张更生, 袁兰党. 一类最优组合批处理码. 数学学报, 2016, 59(2): 267-278 https://doi.org/10.12386/A2016sxxb0024
Dong Dong JIA, Geng Sheng ZHANG, Lan Dang YUAN. A Class of Optimal Combinatorial Batch Code. Acta Mathematica Sinica, Chinese Series, 2016, 59(2): 267-278 https://doi.org/10.12386/A2016sxxb0024

参考文献

[1] Balachandran N., Bhattacharya S., On an extremal hypergraph problem related to combinatorial batch codes, Discrete Appl. Math., 2014, 162: 373-380.
[2] Bhattacharya S., Ruj S., Roy B., Combinatorial batch codes: A lower bound and optimal constructions, Adv. Math. Commun., 2012, 6: 165-174.
[3] Brualdi R. A., Kiernan K. P., Meyer S. A., et al., Combinatorial batch codes and transversal matroids, Adv. Math. Commun., 2010, 4: 419-431.
[4] Bujtás C., Tuza Z., Optimal batch codes: Many items or low retrieval requirement, Adv. Math. Commun., 2011, 5: 529-541.
[5] Bujtás C., Tuza Z., Optimal combinatorial batch codes derived from dual systems, Miskolc. Math. Notes., 2011, 12: 11-23.
[6] Bujtás C., Tuza Z., Combinatorial batch codes: Extremal problems under Hall-type conditions, Electron Notes in Discrete Math., 2011, 38: 201-206.
[7] Bujtás C., Tuza Z., Relaxations of Halls condition: Optimal batch codes with multiple queries, Appl. Anal Discrete Math., 2012, 6: 72-81.
[8] Bujtás C., Tuza Z., Turán numbers and batch codes, Discrete Appl. Math., 2015, 186: 45-55.
[9] Chen J., Zhang S., Zhang G., Optimal combinatorial batch code: monotonicity, lower and upper bounds, Sci. Sin. Math., 2015, 45(3): 311-320 (in Chinese).
[10] Ishai Y., Kushilevitz E., Ostrovsky R., et al., Batch codes and their applications, in: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing STOC'04, New York, USA, 2004, 36: 262-271.
[11] Jia D., Shen Y., Zhang G., A survey of the study of combinatorial batch code (in Chinese), Adv. Math. China, 2015, in press.
[12] Liu X., Zhang S., Zhang G., Combinatorial batch codes based on RTD(q-2, q) (in Chinese), Adv. Math. China, 2015, in press.
[13] Paterson M. B., Stinson D. R., Wei R., Combinatorial batch codes, Adv. Math. Commun., 2009, 3: 13-27.
[14] Ruj S., Roy B., More on combinatorial batch codes, arXiv: 0809.3357v1, 2008.
[15] Silberstein N., Gál A., Optimal combinatorial batch codes based on block designs, Des Codes Cryptogr, Published online, 2014, DOI 10.1007/s10623-014-0007-9.

基金

国家自然科学基金资助项目(11171089, 11371121); 河北省自然科学基金资助项目(A2013205073); 河北师范大学科研基金资助项目(L2015Z02)

PDF(602 KB)

Accesses

Citation

Detail

段落导航
相关文章

/