Improved upper bounds for several variants of group testing [Elektronische Ressource] / vorgelegt von Andreas Allemann

Description

Improved Upper Bounds forSeveral Variants of Group TestingVon der Fakult¨at fur¨ Mathematik, Informatik und Naturwissenschaftender Rheinisch-Westf¨alischen Technischen Hochschule Aachenzur Erlangung des akademischen Grades eines Doktorsder Naturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-MathematikerAndreas Allemannaus BonnBerichter: Universit¨atsprofessor Dr. Eberhard TrieschProfessor Dr. Lutz VolkmannTag der mundlic¨ hen Prufung:¨ 11. November 2003Diese Dissertation ist auf den Internetseiten der Hochschulbibliothekonline verfug¨ bar.iiContentsIntroduction 11 On the Structure of Group Testing 51.1 The Group Testing Model . . . . . . . . . . . . . . . . . . . . 51.2 The Test Information Hypergraph . . . . . . . . . . . . . . . 61.3 Identifying an Unknown Number of Defectives . . . . . . . . 81.4 Identifying a Bounded Number of Defectives . . . . . . . . . . 102 Complete Group Testing 152.1 Variants of Combinatorial Group Testing . . . . . . . . . . . 152.2 Complete Related to (d,n) Group Testing . . . . . . . . . . . 163 The Split and Overlap Algorithm 193.1 Nested Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Overview of the Split and Overlap Algorithm . . . . . . . . . 213.3 Overlapping Subalgorithms . . . . . . . . . . . . . . . . . . . 223.4 Cost Estimate of Subalgorithms . . . . . . . . . . . . . . . . . 273.5 Scaling up Subalgorithms . . . . . . . . . . . . . . . . . . . . 293.6 Fixed Size Algorithms . .

Sujets

• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2003
• Nombre de lectures: 77
• Langue: English

Extrait

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

iii

1 5 5 6 8 10 15 15 16 19 19 21 22 27 29 31 35 39 41 47

iv

CONTENTS

Introduction

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 log 2 x. 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