一类最优组合批处理码
A Class of Optimal Combinatorial Batch Code
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等人提出的未解决问题.
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条件 {{custom_keyword}} /
combinatorial batch code / optimal CBC / dual set system / k-restricted Hall condition {{custom_keyword}} /
[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)
/
〈 | 〉 |