CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Adaptive group testing with a constrained number of positive responses improved

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Discrete Applied Mathematics (0166-218X). Vol. 205 (2016), p. 208-212.
[Artikel, refereegranskad vetenskaplig]

Group testing aims at identifying the defective elements of a set by testing selected subsets called pools. A test gives a positive response if the tested pool contains some defective elements. Adaptive strategies test the pools one by one. Assuming that only a tiny minority of elements are defective, the main objective of group testing strategies is to minimize the number of tests. De Bonis introduced in COCOA 2014 a problem variant where one also wants to limit the number of positive tests, as they have undesirable side effects in some applications. A strategy was given with asymptotically optimal test complexity, subject to a constant factor. In the present paper we reduce the test complexity, making also the constant factor optimal in the limit. This is accomplished by a routine that searches for a single defective element and uses pools of decreasing sizes even after negative responses. An additional observation is that randomization saves a further considerable fraction of tests compared to the deterministic worst case, if the number of permitted positive responses per defective element is small.

Nyckelord: group testing, positive test, adaptive strategy, randomized strategy

Denna post skapades 2016-04-27. Senast ändrad 2016-05-27.
CPL Pubid: 235269


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)


Diskret matematik

Chalmers infrastruktur