グループテスト
Combinatorial group testing in general was later studied more fully by Katona in 1973. Katona introduced the matrix representation of non-adaptive group-testing and produced a procedure for finding the defective in the non-adaptive 1-defective case in no more than t = ⌈ log 2  ( n ) ⌉ {\displaystyle t=\lceil \log _{2}(n)\rceil } tests, which he also proved to be optimal.
In general, finding optimal algorithms for adaptive combinatorial group testing is difficult, and although the computational complexity of group testing has not been determined, it is suspected to be hard in some complexity class.
Although adaptive algorithms offer much more freedom in design, it is known that adaptive group-testing algorithms do not improve upon non-adaptive ones by more than a constant factor in the number of tests required to identify the set of defective items. In addition to this, non-adaptive methods are often useful in practice because one can proceed with successive tests without first analysing the results of all previous tests, allowing for the effective distribution of the testing process.
(2011) introduced COMP, a probabilistic algorithm that requires no more than t = e d ( 1 + δ ) ln  ( n ) {\displaystyle t=ed(1+\delta )\ln(n)} tests to find up to d {\displaystyle d} defectives in n {\displaystyle n} items with a probability of error no more than n − δ {\displaystyle n^{-\delta }} . This is within a constant factor of the t = O ( d log 2  n ) {\displaystyle t=O(d\log _{2}n)} lower bound.
Chan et al. (2011) also provided a generalisation of COMP to a simple noisy model, and similarly produced an explicit performance bound, which was again only a constant (dependent on the likelihood of a failed test) above the corresponding lower bound.
“A method for detecting all defective members in a population by group testing”. Journal of the American Statistical Association 67 (339): 605–608. doi:10.2307/2284447. JSTOR 2284447.
↑ Allemann, Andreas (2013). “An efficient algorithm for combinatorial group testing”. Information Theory, Combinatorics, and Search Theory: 569–596.
1 2 Hu, M. C.; Hwang, F. K.; Wang, Ju Kwei (June 1981). “A Boundary Problem for Group Testing”. SIAM Journal on Algebraic and Discrete Methods 2 (2): 81–87. doi:10.1137/0602011.
↑ Leu, Ming-Guang (28 October 2008). “A note on the Hu–Hwang–Wang conjecture for group testing.”. The ANZIAM Journal 49 (4): 561. doi:10.1017/S1446181108000175.
↑ Riccio, Laura; Colbourn, Charles J. (1 January 2000).
There are two independent classifications for group-testing problems; every group-testing problem is either adaptive or non-adaptive, and either probabilistic or combinatorial.
In probabilistic models, the defective items are assumed to follow some probability distribution and the aim is to minimise the expected number of tests needed to identify the defectiveness of every item. On the other hand, with combinatorial group testing, the goal is to minimise the number of tests needed in a 'worst-case scenario' – that is, create a minmax algorithm – and no knowledge of the distribution of defectives is assumed.
1 2 3 4 5 6 7 8 9 Atia, George Kamal; Saligrama, Venkatesh (March 2012). “Boolean compressed sensing and noisy group testing”. IEEE Transactions on Information Theory 58 (3): 1880–1901. arXiv:0907.1061. doi:10.1109/TIT.2011.2178156.
1 2 3 4 5 6 7 8 9 10 Chun Lam Chan; Pak Hou Che; Jaggi, Sidharth; Saligrama, Venkatesh (1 September 2011), “2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)”, 49th Annual Allerton Conference on Communication, Control, and Computing: pp. 1832–1839, arXiv:1107.4540, doi:10.1109/Allerton.2011.6120391, ISBN 978-1-4577-1817-5
↑ Hung, M.; Swallow, William H. (March 1999). “Robustness of Group Testing in the Estimation of Proportions”. Biometrics 55 (1): 231–237.