Upper and Lower Bounds for Competitive Group Testing

arXiv (Cornell University)

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.

Authors 2

1. Robert Scheidweiler
   Affiliation as printed

   Paderborn , Germany

2. Eberhard Triesch Aachen Lehrstuhl 2 für Mathematik

   RWTH Aachen University

   Affiliation as printed

   Lehrstuhl 2 für Mathematik , RWTH Aachen University , Aachen , Germany