2 Algorithm for Finitely Divisible Items
Our algorithm (both here and in subsequent sections) resembles the non-adaptive binary splitting approach
of [11, 32]. At a high level, we form large groups of items and recursively split them into smaller sub-groups,
then randomly place groups into tests. The decoder works down the resulting tree (see Figure 1), eliminating
groups that are believed to be defective based on the test outcomes, while recursively handling all remaining
groups.
We highlight the following differences compared to the binary splitting approach [11, 32]:
• We use a shorter tree of height γ
0
≤ γ. This is because a given item is placed in a single test at each
level, so the assumption γ = o(log n) prohibits us from having O(log n) levels. We consider γ
0
≤ γ
so that the remaining budget can be used at the final level, and we later optimize γ
0
to minimize the
number of tests.
• In view of the shorter height, we use non-binary splitting; this was considered under adaptive testing in
[36, 17], and our algorithm can be viewed as a non-adaptive counterpart, in the same way that [11, 32]
can be viewed as a non-adaptive counterpart of Hwang’s binary splitting algorithm [21].
• In contrast to the unconstrained setting, we cannot readily use the idea of using N sequences of tests at
each level while only increasing the number of tests by a factor of N = O(1). Here, such an approach
turns out to be highly wasteful in terms of its use of the limited γ budget, and we avoid it altogether.
• At the top level of the tree (excluding the root), we use individual testing (i.e., each node has its own
test). This guarantees that no non-defective node from the second level can “continue” down the tree,
which simplifies our analysis.
2.1 Description of the Algorithm
The levels of the tree, summarized in Figure 1, are indexed by l = 0, 1, . . . , γ
0
. Since testing at the root is
not informative (we will always get a positive outcome), we start our testing procedure at l = 1 (the second
level of nodes in Figure 1). We choose
2
M = (n/k)
γ
0
−1
γ
0
, T
len
= Ck(n/k)
1/γ
0
and T
0
len
= γ
0
k(n/k)
1/γ
0
, where
C is a constant. Here the choice of M is taken to match the near-optimal adaptive splitting algorithm of
[36], and the choices of T
len
and T
0
len
are motivated by the goal of having a number of tests matching the
COMP algorithm (see Table 1). Under these preceding choices, the total number of tests (excluding the last
2
Here and subsequently, we assume for notation convenience that (n/k)
1/γ
and (n/k)
1/γ
0
are integers. Since we focus on
scaling laws, the resulting effect of rounding has no impact on our results.
7
剩余35页未读，继续阅读
易小侠
- 粉丝: 6545
- 资源: 9万+
我的内容管理
展开
最新资源
- 贵州煤矿矿井水分类与处理策略：悬浮物、酸性与非酸性
- 醛固酮增多症肾上腺静脉采样对比：ACTH后LR-CAV的最优评估
- 开源云连接传感器监控平台：农业土壤湿度远程监测
- 母婴用品企业年度生产计划线性规划优化模型：实证与应用
- 井下智能变电站：Rogowski线圈电流检测系统的研发与性能验证
- 霍州矿区煤巷稳定性分析及支护策略
- ARM嵌入式系统远程软件更新方案：基于TFTP协议
- 煤炭选煤中汞分布规律与洗选脱汞效果
- 提升码垛机器人性能：拉格朗日动力学模型与滑模模糊控制的应用
- 增强现实技术提升学前手写教学：设计与开发案例
- 不规则工作面沉陷三角剖分算法提升与应用
- 卡尔曼滤波在瞬变电磁干扰压制中的应用研究
- 煤矿安全能力研究：理论与系统构建
- LonWorks总线技术在斜巷运输车辆定位与跑车防护中的应用
- 神东煤炭集团高效煤粉锅炉系统：节能环保新实践
- Ti/SnO2+Sb2Ox/PbO2电极分形维数与电催化性能研究
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
