Improved Upper Bounds for Several Variants of Group Testing
VonderFakult¨atf¨urMathematik,InformatikundNaturwissenschaften derRheinisch-Westfa¨lischenTechnischenHochschuleAachen zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften genehmigte Dissertation
vorgelegt von
Diplom-Mathematiker Andreas Allemann aus Bonn
Berichter:Universita¨tsprofessorDr.EberhardTriesch Professor Dr. Lutz Volkmann
Tagdermu¨ndlichenPr¨ufung:11.November2003
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek onlineverf¨ugbar.
ii
Contents
Introduction 1 On the Structure of Group Testing 1.1 The Group Testing Model . . . . . . . . . . . . . . . . . . . . 1.2 The Test Information Hypergraph . . . . . . . . . . . . . . . 1.3 Identifying an Unknown Number of Defectives . . . . . . . . 1.4 Identifying a Bounded Number of Defectives . . . . . . . . . . 2 Complete Group Testing 2.1 Variants of Combinatorial Group Testing . . . . . . . . . . . 2.2 Complete Related to (d, n. . . . . . . . . . .) Group Testing 3 The Split and Overlap Algorithm 3.1 Nested Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Overview of the Split and Overlap Algorithm . . . . . . . . . 3.3 Overlapping Subalgorithms . . . . . . . . . . . . . . . . . . . 3.4 Cost Estimate of Subalgorithms . . . . . . . . . . . . . . . . . 3.5 Scaling up Subalgorithms . . . . . . . . . . . . . . . . . . . . 3.6 Fixed Size Algorithms . . . . . . . . . . . . . . . . . . . . . . 3.7 Cost Estimate of Fixed Size Algorithms . . . . . . . . . . . . 3.8 Main Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Cost Estimate of Main Algorithm . . . . . . . . . . . . . . . . Bibliography
Group testing is a class of search problems, in which we typically have a set ofnitems, each of which is either good or defective. A test on an arbitrary group (subset) of items reveals either that all items in the group are good or that at least one of the items is defective, but not how many or which items are defective. The aim is to identify all items as either good or defective using as few tests as possible. We focus on thesequentialcase, in which the results of preceding tests may be used to determine the next test group. Thenonadaptivecase, in which all test groups have to be specified in advance, is a very different problem with few connections to the sequential case. We distinguish betweenprobabilistic(average case) andcombinatorial (worst case) group testing problems. In the former, we try to minimize the expected number of tests under a given probability distribution of the defectives. In the latter, the aim is to minimize the maximum number of tests required. In this thesis, logxalways denotes log2x. Letdxe(bxc) denote the smallest (largest) integer greater (less) than or equal tox. The history of group testing begins with the probabilistic problem as-suming that each item is defective with some probabilitypindependent of all other items, also called thebinomial group testingproblem. In 1943, Dorfman [5] was the first to study group testing, motivated by the need to screen large populations for infectious diseases economically by testing pools of several blood samples for antibodies. A detailed account of the early history of group testing was given by Du and Hwang [6, Section 1.1]. Motivated by applications in industrial testing, Sobel and Groll [19] in-troduced a restricted class of algorithms called thenested class a group: if of at least two items is contaminated, that is, known to contain a defec-tive, a nested algorithm always uses a subset of this group as the next test group. Sobel and Groll [19] gave a recursive definition of an optimal nested algorithm for the binomial group testing problem with parameterp, which was simplified later by Hwang [12]. Sobel [18] improved this algorithm by using special procedures involving overlapping test groups for contaminated groups containing 2 or 3 items. Chen, Hsu, and Sobel [3], see also Hsu [9], gave a construction based on choosing the next test group by one of two approaches: either trying to achieve a probability of a positive test result 1