Upper and Lower Bounds for Competitive Group Testing

Abstract

We consider competitive algorithms for adaptive group testing problems. In the first part of the paper, we develop an algorithm with competitive constant c < 1.452 thus improving the up to now best known algorithms with constants 1.5+epsilon from 2003. In the second part, we prove the first nontrivial lower bound for competitive constants, namely that c is always larger than 1.31.