最优组合批处理码的单调性质及上下界

具有参数n,k和m的组合批处理码可以看作一个n元集以及它的m个子集B_1,B_2,…,B_m组成的集合系统,满足对于任意k个元素都能通过从每个子集中至多取一(可以一般化为t)个元素来取得.一个优化问题是,确定m个子集中元素总数|B_1|+|B_2|+…+|B_m|的最小值N(n,k,m).这种问题不仅具有理论意义,而且有着重要的应用价值.本文研究N(n,k,m)的变化规律,给出N(n,k,m)的一个上下界,当2≤km≤n-3时,如果m+1-k≥[(k+1)~(1/2)],(n-m)k+m≥N(n,k,m)≥2n-m+k-6+[2(k+1)~(1/2)];如果m+1-k[(k+1)~(1/2)],(n-m)k+m≥N(n,k,m)≥2n-6+[1+(k+1)/(m-k+1)].然后确定N(m+3,4,m)=m+9(当m≥6时),N(8,4,5)=15,得到的结果部分解决了Paterson等人提出的未解决问题.