论文标题
一般设定系统的小组测试
Group Testing on General Set-Systems
论文作者
论文摘要
小组测试是编码理论和组合学中的基本问题之一，其中一个人是从给定的地面组中确定受污染项目的子集。由于其在诊断病毒学中的应用，包括对新型冠状病毒的泳池测试，最近对小组测试引起了人们的兴趣。大多数现有在小组测试上的作品重点关注\ emph {sustry}的设置，其中任何大小$ d $的子集中的大小$ v $ size $ n $的$ d $都可能受到污染。在这项工作中，我们将使用任意受污染集的任意设定系统考虑组测试的{\ em广义}版本。广义问题的特征是$ h =（v，e）$，其中$ v $代表地面套件，E $中的边缘$ e \代表潜在受污染的集合。广义小组测试的问题是由实际设置所激发的，在这种情况下，由于社会动态，地理局限性或其他考虑因素，并非所有给定尺寸$ d $的子集都可能污染，因此存在很容易排除的子集。例如，在泳池测试的背景下，边缘集$ e $可能包括家庭，工作团队或教室中的学生，即可能会相互污染的子集。研究广义设置的目标是利用$ h =（v，e）$的其他知识来显着减少所需的测试数量。本文考虑了自适应和非自适应组测试，并做出以下贡献。首先，对于非自适应设置，我们表明，为组测试的通用版本找到一个最佳解决方案是NP-HARD。对于此设置，我们提出了一个需要$ O（d \ log {| e |}）$ tests的解决方案，其中$ d $是e $ in e $的设置$ e \的最大尺寸。我们的解决方案将提供的解决方案推广到传统设置，并显示为有序尺寸$ o（\ log {| e |}）$，用于具有``大''对称差异的边缘的超图。对于自适应设置，当$ e $中的边缘恰好是$ d $时，我们提供了一个大小$ o的解决方案（\ log {| e |} + d \ log^2 {d} {d} {d {d}）$，该$接近$ω（\ log log {| e | e |} + d）$的下限。
Group testing is one of the fundamental problems in coding theory and combinatorics in which one is to identify a subset of contaminated items from a given ground set. There has been renewed interest in group testing recently due to its applications in diagnostic virology, including pool testing for the novel coronavirus. The majority of existing works on group testing focus on the \emph{uniform} setting in which any subset of size $d$ from a ground set $V$ of size $n$ is potentially contaminated. In this work, we consider a {\em generalized} version of group testing with an arbitrary set-system of potentially contaminated sets. The generalized problem is characterized by a hypergraph $H=(V,E)$, where $V$ represents the ground set and edges $e\in E$ represent potentially contaminated sets. The problem of generalized group testing is motivated by practical settings in which not all subsets of a given size $d$ may be potentially contaminated, rather, due to social dynamics, geographical limitations, or other considerations, there exist subsets that can be readily ruled out. For example, in the context of pool testing, the edge set $E$ may consist of families, work teams, or students in a classroom, i.e., subsets likely to be mutually contaminated. The goal in studying the generalized setting is to leverage the additional knowledge characterized by $H=(V,E)$ to significantly reduce the number of required tests. The paper considers both adaptive and non-adaptive group testing and makes the following contributions. First, for the non-adaptive setting, we show that finding an optimal solution for the generalized version of group testing is NP-hard. For this setting, we present a solution that requires $O(d\log{|E|})$ tests, where $d$ is the maximum size of a set $e \in E$. Our solutions generalize those given for the traditional setting and are shown to be of order-optimal size $O(\log{|E|})$ for hypergraphs with edges that have ``large'' symmetric differences. For the adaptive setting, when edges in $E$ are of size exactly $d$, we present a solution of size $O(\log{|E|}+d\log^2{d})$ that comes close to the lower bound of $Ω(\log{|E|} + d)$.
