| Paper ID | D4-S7-T3.2 |
| Paper Title |
Improved algorithms for non-adaptive group testing with consecutive positives |
| Authors |
Thach V. Bui, University of Science, Ho Chi Minh city, Vietnam, Viet Nam; Mahdi Cheraghchi, University of Michigan, Ann Arbor, MI, USA, United States; Thuc D. Nguyen, University of Science, Ho Chi Minh City, Vietnam, Viet Nam |
| Session |
D4-S7-T3: Group Testing |
| Chaired Session: |
Friday, 16 July, 00:00 - 00:20 |
| Engagement Session: |
Friday, 16 July, 00:20 - 00:40 |
| Abstract |
The goal of group testing is to efficiently identify a few specific items, called positives, in a large population of items via tests. A test is an action on a subset of items that returns positive if the subset contains at least one positive and negative otherwise. In non-adaptive group testing, all tests are independent, can be performed in parallel, and represented as a measurement matrix. In this work, we consider non-adaptive group testing with consecutive positives in which the items are linearly ordered and the positives are consecutive in that order. We present two algorithms for efficiently identifying consecutive positives. In particular, without storing measurement matrices, we can identify up to $d$ consecutive positives with $2 \log_2{\frac{n}{d}} + 2d$ ($4 \log_2{\frac{n}{d}} + 2d$, resp.) tests in $O \left( \log_2^2{\frac{n}{d}} + d \right)$ ($O \left( \log_2{\frac{n}{d}} + d \right)$, resp.) time. These results significantly improve the state-of-the-art scheme in which it takes $5 \log_2{\frac{n}{d}} + 2d + 21$ tests to identify the positives in $O \left( \frac{n}{d} \log_2{\frac{n}{d}} + d^2 \right)$ time with the measurement matrices associated with the scheme stored somewhere.
|
