×

A zig-zag approach for competitive group testing. (English) Zbl 1304.90073

Summary: In many fault-detection problems, we want to identify defective items from a set of \(n\) items using the minimum number of tests. Group testing is a scenario in which each test is on a subset of items and determines whether the subset contains at least one defective item. In practice, the number \(d\) of defective items is often unknown in advance. In this paper, we present a new algorithm for the above group testing problem and prove that it has very good performance guarantee. More specifically, the number of tests used by the new algorithm is bounded from above by \(d\, \log(n/d) + 3d + O(\log^{2}d)\). The new algorithm is designed based on a zig-zag approach that has not been studied before and is intuitive and easy to implement. When \(0< d < \rho_{0}n\) where \(\rho_{0} = 1 - 4/e^{2} = 0.45\ldots\), which holds for most practical applications, our new algorithm has better performance guarantee than any previous best result. Computational results show that the new algorithm has very good practical performances.

MSC:

90B25 Reliability, availability, maintenance, inspection in operations research
62P30 Applications of statistics in engineering and industry; control charts
62N05 Reliability and life testing
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abolnikov L, Dukhovny A (2003) Optimization in HIV screening problems. J. Appl. Math. Stochastic Anal. 16:361-374. · Zbl 1044.92027
[2] Bar-Lev SK, Parlar M, Perry D, Stadje W, Schouten FAVDD (2007) Applications of bulk queues to group testing models with incomplete identification. Eur. J. Oper. Res. 183:226-237. · Zbl 1127.90017
[3] Bar-Noy A, Hwang FK, Kessler I, Kutten S (1994) A new competitive algorithm for group testing. Discrete Appl. Math. 52:29-38.
[4] Barillot E, Lacroix B, Cohen D (1991) Theoretical analysis of library screening using a n-dimensional pooling strategy. Nucleic Acids Res. 19:6241-6247.
[5] Bruno WJ, Balding DJ, Knill EH, Bruce D, Whittaker C, Doggett N, Stallings R, Torney DC (1995) Design of efficient pooling experiments. Genomics 26:21-30.
[6] Claeys D, Walraevens J, Laevens K, Bruneel H (2010) A queueing model for general group screening policies and dynamic item arrivals. Eur. J. Oper. Res. 207:827-835. · Zbl 1205.90086
[7] Cormode G, Muthukrishnan S (2005) What’s hot and what’s not: Tracking most frequent items dynamically. ACM Trans. Database Systems 30:249-278.
[8] Damaschke P, Sheikh Muhammad A (2012) Randomized group testing both query-optimal and minimal adaptive. Proc. 38th Internat. Conf. Current Trends in Theory and Practice Comput. Sci. (SOFSEM 2012), Lecture Notes in Computer Science, Vol. 7147 (Springer, Berlin), 214-225. · Zbl 1298.68052
[9] Dorfman R (1943) The detection of defective members of large populations. Ann. Math. Statist. 14:436-440.
[10] Du DZ, Hwang FK (1993) Competitive group testing. Discrete Appl. Math. 45:221-232. · Zbl 0784.90046
[11] Du DZ, Hwang FK (2000) Combinatorial Group Testing and Its Applications, 2nd ed. (World Scientific, Singapore).
[12] Du DZ, Park H (1994) On competitive group testing. SIAM J. Comput. 23:1019-1025.
[13] Du DZ, Xue GL, Sun SZ, Cheng SW (1994) Modifications of competitive group testing. SIAM J. Comput. 23:82-96. · Zbl 0802.68009
[14] Goodrich MT, Hirschberg DS (2008) Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis. J. Combin. Optim. 15:95-121. · Zbl 1182.94005
[15] Hong EH, Ladner RE (2002) Group testing for image compression. IEEE Trans. Image Processing 11:901-911.
[16] Hong YW, Scaglione A (2004) On multiple access for distributed dependent sources: A content-based group testing approach. Proc. IEEE Inform. Theory Workshop, San Antonio, Texas, 298-303.
[17] Hwang FK (1972) A method for detecting all defective members in a population by group testing. J. Amer. Statist. Assoc. 67: 605-608. · Zbl 0247.62010
[18] Kahng AB, Reda S (2006) New and improved BIST diagnosis methods from combinatorial group testing theory. IEEE Trans. Comput.-Aided Design Integrated Circuits Systems 25:533-543.
[19] Kautz WH, Singleton RC (1964) Nonrandom binary superimposed codes. IEEE Trans. Inform. Theory 10:363-377. · Zbl 0133.12402
[20] Li CH (1962) A sequential method for screening experimental variables. J. Amer. Statist. Assoc. 57:455-477. · Zbl 0105.12202
[21] Manasse M, McGeoch LA, Sleator D (1988) Competitive algorithms for on-line problems. Proc. 20th Annual ACM Sympos. Theory Comput. (ACM, New York), 322-333.
[22] Mezard M, Toninelli C (2011) Group testing with random pools: Optimal two-stage algorithms. IEEE Trans. Inform. Theory 57: 1736-1745. · Zbl 1366.62152
[23] Schlaghoff J, Triesch E (2005) Improved results for competitive group testing. Combinatorics, Probab. Comput. 14:191-202. · Zbl 1062.68048
[24] Sleator D, Tarjan R (1985) Amortized efficiency of list update and paging rules. Comm. ACM 28:202-208.
[25] Sobel M, Groll PA (1959) Group testing to eliminate efficiently all defectives in a binomial sample. Bell System Technical J. 38: 1179-1252.
[26] Wein LM, Zenios SA (1996) Pooled testing for HIV screening: Capturing the dilution effect. Oper. Res. 44:543-569. [Abstract] · Zbl 0865.90091
[27] Wolf J (1985) Born again group testing: Multiaccess communications. IEEE Trans. Inform. Theory 31:185-191. · Zbl 0586.94011
[28] Zenios SA, Wein LM (1998) Pooled testing for HIV prevalence estimation: Exploiting the dilution effect. Statist. Medicine 17:1447-1467.
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.