Improved upper bounds for several variants of group testing

Allemann, Andreas; Triesch, Eberhard

doi:urn:nbn:de:hbz:82-opus-7049

Improved upper bounds for several variants of group testing

Allemann, Andreas (Author)

2003

Verantwortlichkeitsangabevorgelegt von Andreas Allemann

ImpressumAachen : Publikationsserver der RWTH Aachen University 2003

UmfangIV, 48 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2003

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Triesch, Eberhard (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2003-11-11

Online
URN: urn:nbn:de:hbz:82-opus-7049
DOI: 10.18154/RWTH-CONV-120900
URL: http://publications.rwth-aachen.de/record/59084/files/59084.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Gruppentesten (Genormte SW) ; Mathematik (frei) ; group testing (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Gruppentesten ist eine Klasse von Suchproblemen mit dem Ziel, jedes von n Elementen entweder als gut oder defekt zu identifizieren. Wir dürfen Tests auf beliebigen Teilmengen durchführen, die anzeigen ob die getestete Gruppe nur gute Elemente oder mindestens ein defektes Element enthält. Im (d,n)- und verallgemeinerten (d,n)-Gruppentestproblem ist bekannt, dass genau beziehungsweise höchstens d defekte Elemente vorhanden sind und wir versuchen, die Zahl der benötigten Tests im worst case zu minimieren. In dieser Dissertation führen wir eine Verallgemeinerung dieser Probleme ein, bei der der Fall, dass mehr als d Elemente defekt sind, ebenfalls erkannt werden muss und beweisen, dass die Lösung des neuen Problems genau einen Test mehr benötigt als die des (d,n)-Gruppentestproblems. Das Hauptergebnis ist ein neuer Algorithmus für all diese Probleme, dessen Anzahl benötigter Tests für n/d >= 2 um weniger als 0.255d + 0.5log2 d + 5.5 über der informationstheoretischen unteren Schranke liegt. Für d >= 10 liegt dies unter der besten in der Literatur bekannten oberen Schranke von d - 1 zusätzlichen Tests.

Group testing is a class of search problems, in which we aim to identify all of n items as either good or defective. We may perform tests on arbitrary subsets, which indicate whether the tested group contains only good items or at least one defective. In the (d,n) and generalized (d,n) group testing problems, it is known that the number of defectives is exactly d respectively at most d and we try to minimize the worst case number of tests. In this thesis, we introduce a generalization of these problems by requiring the case of more than d defectives to be detected as well and prove that solving the new problem needs exactly one more test than the (d,n) group testing problem. The major result is a new algorithm for all these problems whose required number of tests is for n/d >= 2 less than 0.255d + 0.5log2 d + 5.5 above the information lower bound. For d >= 10, this is below the best known upper bound of d - 1 additional tests given in the literature.

OpenAccess:
PDF
(additional files)