论文标题
竞争小组测试的上限和下限
Upper and Lower Bounds for Competitive Group Testing
论文作者
论文摘要
我们考虑用于自适应组测试问题的竞争算法。在本文的第一部分中，我们开发了一种具有竞争力常数C <1.452的算法，因此从2003年开始使用常数为1.5+Epsilon的算法，从而改善了算法。在第二部分中，我们证明了第一个非平凡的下降限制，即竞争常数，即C始终大于1.31。
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.
