摘要 Abstract
群组检测作为一个具有多样应用的问题,传统上假设节点状态之间相互独立。然而,近期的研究聚焦于现实世界中的场景,这些场景往往涉及节点之间的相关性,挑战了现有模型中的简化假设。在本文中,我们考虑了一个全面的模型,用于描述节点状态之间的任意统计相关性。为了有效地捕捉并利用这些相关性,我们通过超图建模该问题,并受到[GLS22]的启发,同时在超边添加概率质量函数。利用这一模型,我们首先设计了一种新颖的贪心自适应算法,能够进行信息量大的测试并动态更新分布。性能分析提供了所需测试次数的上界,这些上界仅依赖于潜在概率分布的熵以及感染的平均数量。我们证明该算法在有相关性的群组检测设置中恢复或改进了所有已知结果。此外,我们给出了算法在顺序意义上最优的一些图族,并举例说明了算法或其分析不紧致的情况。随后,我们将提出的群组检测框架一般化到两个方向,即噪声群组检测和半非自适应群组检测。在两种情况下,我们都提供了关于所需测试次数的新理论界限。
Group testing, a problem with diverse applications across multiple disciplines, traditionally assumes independence across nodes' states. Recent research, however, focuses on real-world scenarios that often involve correlations among nodes, challenging the simplifying assumptions made in existing models. In this work, we consider a comprehensive model for arbitrary statistical correlation among nodes' states. To capture and leverage these correlations effectively, we model the problem by hypergraphs, inspired by [GLS22], augmented by a probability mass function on the hyper-edges. Using this model, we first design a novel greedy adaptive algorithm capable of conducting informative tests and dynamically updating the distribution. Performance analysis provides upper bounds on the number of tests required, which depend solely on the entropy of the underlying probability distribution and the average number of infections. We demonstrate that the algorithm recovers or improves upon all previously known results for group testing settings with correlation. Additionally, we provide families of graphs where the algorithm is order-wise optimal and give examples where the algorithm or its analysis is not tight. We then generalize the proposed framework of group testing with general correlation in two directions, namely noisy group testing and semi-non-adaptive group testing. In both settings, we provide novel theoretical bounds on the number of tests required.