Searching for Search Strategies: Solutions to Strict Group Testing Problem Instances

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/249959
Download file(s):
File Description SizeFormat 
249959.pdfFulltext590.33 kBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Searching for Search Strategies: Solutions to Strict Group Testing Problem Instances
Authors: Grankvist, David
Abstract: Group testing is the problem of identifying a set of d defectives amongst a much larger set of n elements. To this end, the searcher is able to perform tests on groups of elements, each test revealing whether a defective is present within a group. In multi-stage group testing, the search can be subdivided into s stages where all tests within the same stage are run in parallel. This allows for adaptations to be made mid-search based on partial knowledge, potentially reducing the total number of tests. In strict group testing, there exists the additional possibility that more than d defectives exist. In such scenarios, the searcher is obligated to report this fact. The individual computation steps of group testing, the tests, are assumed to be incredibly costly, implying that search strategies can not be evaluated based solely on asymptotic optimality. Therefore, the approach is to solve specific problem instances optimally by devising tailor-made strategies. The goal of this thesis work is to devise such strategies for previously unsolved multi-stage strict group testing instances. Part of this goal, as well as being a goal on its own, is the study of related subproblems. The chosen methodology to accomplish the goals is rather simplistic. Each derivation consists of making assumptions about the number of tests required for the given instance, and then applying various theoretical tools in order to systematically narrow down the search space. Multiple instances of both the main problem and the related subproblems are solved, with the latter being a key step in accomplishing the former. Moreover, the subproblems are studied further in order to gain insights for future work. In conclusion, it is illustrated in this thesis work both that simple reduction arguments are effective in this context and that it is worthwhile to study subproblems as independent instances.
Keywords: Data- och informationsvetenskap;Computer and Information Science
Issue Date: 2017
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/249959
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.