On the cut-off point for combinatorial group testing. (English) Zbl 0924.68170
Summary: The following problem is known as group testing problem for \(n\) objects. Each object can be essential (defective) or non-essential (intact). The problem is to determine the set of essential objects by asking queries adaptively. A query can be identified with a set \(Q\) of objects and the query \(Q\) is answered by 1 if \(Q\) contains at least one essential object and by 0 otherwise. In the statistical setting the objects are essential, independently of each other, with a given probability \(p<1\) while in the combinatorial setting the number \(k< n\) of essential objects is known. The cut-off point of statistical group testing is equal to \(p^*= {1\over 2}(3- \sqrt 5)\), i.e., the strategy of testing each object individually minimizes the average number of queries iff \(p\geq p^*\) or \(n= 1\). In the combinatorial setting the worst case number of queries is of interest. It has been conjectured that the cut-off point of combinatorial group testing is equal to \(\alpha^*= {1\over 3}\), i.e., the strategy of testing \(n- 1\) objects individually minimizes the worst case number of queries iff \(k/n\geq \alpha^*\) and \(k< n\). Some results in favor of this conjecture are proved.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
Keywords:
group testing problemReferences:
| [1] | Ahlswede, R.; Wegener, I., Search Problems (1987), Wiley: Wiley New York · Zbl 0647.90023 |
| [2] | Angluin, D., Queries and concept learning, Machine Learning, 2, 318-342 (1988) · Zbl 1470.68050 |
| [3] | Blum, A.; Hellerstein, L.; Littlestone, N., Learning in the presence of finitely or infinitely many irrelevant attributes, J. Comput. System Sci., 50, 32-40 (1995) · Zbl 0826.68100 |
| [4] | Bshouty, N. H.; Hellerstein, L., Attribute-efficient learning in query and mistake-bound models, (Proceedings of the 9th Conference on Computational Learning Theory COLT’96 (1996)), 235-243 |
| [5] | Dorfman, R., The detection of defective members of large populations, Ann. Math. Statist., 14, 436-440 (1943) |
| [6] | Du, D.; Hwang, F., Minimizing a combinatorial function, SIAM J. Algebraic Discrete Methods, 3, 523-528 (1982) · Zbl 0504.05006 |
| [7] | Hegedüs, T.; Indyk, P., On learning disjunctions of zero-one threshold functions with queries, (Technical Report (1997), Univ. of Helsinki) |
| [8] | Hellerstein, L.; Pillaipakkamnatt, K.; Raghavan, V.; Wilkins, D., How many queries are needed to learn, J. ACM, 43, 840-862 (1996) · Zbl 0885.68123 |
| [9] | Hu, M.; Hwang, F.; Wang, J., A boundary problem for group testing, SIAM J. Algebraic Discrete Methods, 2, 81-87 (1981) · Zbl 0506.05002 |
| [10] | Kumar, S., Group-testing to classify all units in a trinomial sample, Studia Sci. Math. Hungar., 5, 229-247 (1970) · Zbl 0245.62031 |
| [11] | Picard, C., Théorie des Questionnaires (1965), Gauthier-Villars: Gauthier-Villars Paris · Zbl 0128.39002 |
| [12] | Sobel, M., Group testing to classify efficiently all defectives in a binomial sample, (Machol, Information and Decision Processes (1960), McGraw-Hill: McGraw-Hill New York), 127-161 |
| [13] | Sobel, M., Binomial and hypergeometric group testing, Studia Sci. Math. Hungar., 3, 19-42 (1968) · Zbl 0165.21702 |
| [14] | Sobel, M.; Groll, P. A., Group testing to classify efficiently all defectives in a binomial sample, Bell Systems Techn. J., 38, 1179-1259 (1959) |
| [15] | Sterrett, A., On the detection of defective members of large populations, Ann. Math. Stat., 28, 1033-1036 (1957) · Zbl 0079.35504 |
| [16] | Uehara, R.; Tsuchida, K.; Wegener, I., Optimal attribute-efficient learning of disjunctions, parity, and threshold functions, (Proceedings of 3rd European Conference on Computational Learning Theory. Proceedings of 3rd European Conference on Computational Learning Theory, EuroColt, Lecture Notes in Artificial Intelligence, vol. 1208 (1997), Springer: Springer Berlin), 171-184 |
| [17] | Ungar, P., The cut-off point for group testing, Commun. Pure Appl. Math., 13, 49-54 (1960) · Zbl 0093.15501 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
