Searching for Search Strategies: Solutions to Strict Group Testing Problem Instances
| dc.contributor.author | Grankvist, David | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers) | sv |
| dc.contributor.department | Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers) | en |
| dc.date.accessioned | 2019-07-03T14:28:15Z | |
| dc.date.available | 2019-07-03T14:28:15Z | |
| dc.date.issued | 2017 | |
| dc.description.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. | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12380/249959 | |
| dc.language.iso | eng | |
| dc.setspec.uppsok | Technology | |
| dc.subject | Data- och informationsvetenskap | |
| dc.subject | Computer and Information Science | |
| dc.title | Searching for Search Strategies: Solutions to Strict Group Testing Problem Instances | |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.degree | Master Thesis | en |
| dc.type.uppsok | H | |
| local.programme | Computer science – algorithms, languages and logic (MPALG), MSc |
Ladda ner
Original bundle
1 - 1 av 1
Hämtar...
- Namn:
- 249959.pdf
- Storlek:
- 590.33 KB
- Format:
- Adobe Portable Document Format
- Beskrivning:
- Fulltext