Sequential group testing with graph constraints
Sequential group testing with graph constraints
复制标题
具有图约束的顺序组测试
DOI：
10.1109/itw.2012.6404678
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Morteza Zadimoghaddam
中科院分区：
文献类型：
--
作者：
Amin Karbasi;Morteza Zadimoghaddam
在传统的分组测试中，目标是通过将N的任意子集分组到不同的池中来检测大总体N中的缺陷项目D的小子集。每个组测试T的结果是取决于该组是否包含缺陷项的二进制输出。主要的挑战是最小化识别集合D所需的池的数量。受网络监控和感染传播中的应用的启发，我们考虑了图约束的组测试问题。与传统的分组测试不同，这里的测试是可接受的，如果它诱导出一个连通子图H G。与以前的工作中使用的非自适应池化过程相比，我们首先表明，通过利用自适应策略，可以大大减少测试的数量。更具体地说，对于任何图G，我们设计了一个2-近似算法（因此是阶最优的）来定位缺陷项D的集合。为了在自适应和非自适应策略之间获得一个很好的折衷，我们设计了一个多阶段算法。特别地，我们证明了如果缺陷项的集合是均匀分布的，则l-阶段池化策略可以在O（l·|D|·|N| 1/l）测试，平均值。1、对于log（|N|）阶段，测试次数减少到4次|D|（|N|），这反过来又是最优顺序。
In conventional group testing, the goal is to detect a small subset of defecting items D in a large population N by grouping arbitrary subset of N into different pools. The result of each group test T is a binary output depending on whether the group contains a defective item or not. The main challenge is to minimize the number of pools required to identify the set D. Motivated by applications in network monitoring and infection propagation, we consider the problem of group testing with graph constraints. As opposed to conventional group testing where any subset of items can be pooled, here a test is admissible if it induces a connected subgraph H ⊂ G. In contrast to the non-adaptive pooling process used in previous work, we first show that by exploiting an adaptive strategy, one can dramatically reduce the number of tests. More specifically, for any graph G, we devise a 2-approximation algorithm (and hence order optimal) that locates the set of defective items D. To obtain a good compromise between adaptive and non-adaptive strategies, we then devise a multi-stage algorithm. In particular, we show that if the set of defective items are uniformly distributed, then an l-stage pooling strategy can identify the defective set in O(l·|D|·|N|1/l) tests, on the average. In particular, for l = log(|N|) stages, the number of tests reduces to 4|D| log(|N|), which in turn is order optimum.