{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:59084"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:59084","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Improved upper bounds for several variants of group testing","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Allemann, Andreas"],"institution":"Publikationsserver der RWTH Aachen University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Triesch, Eberhard"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2003,"date_issued":"2003","date_published":"2003","updated_at":"2026-07-30T19:42:31Z","subjects":["info:eu-repo/classification/ddc/510","Gruppentesten","Mathematik","group testing"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-120900%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-120900%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-120900%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/59084","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Triesch, Eberhard"]},{"key":"dc:creator","label":"Author","values":["Allemann, Andreas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2003"]},{"key":"dc:publisher","label":"Institution","values":["Publikationsserver der RWTH Aachen University"]},{"key":"dc:relation","label":"Dc Relation","values":["info:eu-repo/semantics/altIdentifier/doi/10.18154/RWTH-CONV-120900","info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-7049"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["info:eu-repo/classification/ddc/510","Gruppentesten","Mathematik","group testing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/record/59084","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-120900%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University IV, 48 S. : graph. Darst. (2003). doi:10.18154/RWTH-CONV-120900 = Aachen, Techn. Hochsch., Diss., 2003"]},{"key":"dc:title","label":"Title","values":["Improved upper bounds for several variants of group testing"]}]}],"canonical_facts":{"dc:contributor":["Triesch, Eberhard"],"dc:coverage":["DE"],"dc:creator":["Allemann, Andreas"],"dc:date":["2003"],"dc:description":["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."],"dc:identifier":["https://publications.rwth-aachen.de/record/59084","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-120900%22"],"dc:language":["eng"],"dc:publisher":["Publikationsserver der RWTH Aachen University"],"dc:relation":["info:eu-repo/semantics/altIdentifier/doi/10.18154/RWTH-CONV-120900","info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-7049"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University IV, 48 S. : graph. Darst. (2003). doi:10.18154/RWTH-CONV-120900 = Aachen, Techn. Hochsch., Diss., 2003"],"dc:subject":["info:eu-repo/classification/ddc/510","Gruppentesten","Mathematik","group testing"],"dc:title":["Improved upper bounds for several variants of group testing"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:42:31Z"}