##### Supplementary
• Appears in Collections:

#### Conference Paper: Non-adaptive complex group testing with multiple positive sets

Title Non-adaptive complex group testing with multiple positive sets Chin, FYLLeung, HCMYiu, SM combinatorial group testingknock-out studynon-adaptive complex group testingpooling design 2011 Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ The 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Tokyo, Japan, 23-25 May 2011. In Lecture Notes in Computer Science, 2011, v. 6648, p. 172-183 How to Cite? Given n items with at most d of them having a particular property (referred as positive items), a single test on a selected subset of them is positive if the subset contains any positive item. The non-adaptive group testing problem is to design how to group the items to minimize the number of tests required to identify all positive items in which all tests are performed in parallel. This problem is well-studied and algorithms exist that match the lower bound with a small gap of logd asymptoticically. An important generalization of the problem is to consider the case that individual positive item cannot make a test positive, but a combination of them (referred as positive subsets) can do. The problem is referred as the non-adaptive complex group testing. Assume there are at most d positive subsets whose sizes are at most s, existing algorithms either require Ω(logs n) tests for general n or O((s+d/d) log n) tests for some special values of n . However, the number of items in each test cannot be very small or very large in real situation. The above algorithms cannot be applied because there is no control on the number of items in each test. In this paper, we provide a novel and practical derandomized algorithm to construct the tests, which has two important properties. (1) Our algorithm requires only O((d+s)d+s+1/(ddss log n) tests for all positive integers n which matches the upper bound on the number of tests when all positive subsets are singletons, i.e. s = 1. (2) All tests in our algorithm can have the same number of tested items k. Thus, our algorithm can solve the problem with additional constraints on the number of tested items in each test, such as maximum or minimum number of tested items. © 2011 Springer-Verlag. LNCS v. 6648 is conference proceedings of TAMC 2011 http://hdl.handle.net/10722/135706 0302-97432005 Impact Factor: 0.3022015 SCImago Journal Rankings: 0.252 References in Scopus

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorLeung, HCMen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2011-07-27T01:47:00Z-
dc.date.available2011-07-27T01:47:00Z-
dc.date.issued2011en_HK
dc.identifier.citationThe 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Tokyo, Japan, 23-25 May 2011. In Lecture Notes in Computer Science, 2011, v. 6648, p. 172-183en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/135706-
dc.descriptionLNCS v. 6648 is conference proceedings of TAMC 2011-
dc.description.abstractGiven n items with at most d of them having a particular property (referred as positive items), a single test on a selected subset of them is positive if the subset contains any positive item. The non-adaptive group testing problem is to design how to group the items to minimize the number of tests required to identify all positive items in which all tests are performed in parallel. This problem is well-studied and algorithms exist that match the lower bound with a small gap of logd asymptoticically. An important generalization of the problem is to consider the case that individual positive item cannot make a test positive, but a combination of them (referred as positive subsets) can do. The problem is referred as the non-adaptive complex group testing. Assume there are at most d positive subsets whose sizes are at most s, existing algorithms either require Ω(logs n) tests for general n or O((s+d/d) log n) tests for some special values of n . However, the number of items in each test cannot be very small or very large in real situation. The above algorithms cannot be applied because there is no control on the number of items in each test. In this paper, we provide a novel and practical derandomized algorithm to construct the tests, which has two important properties. (1) Our algorithm requires only O((d+s)d+s+1/(ddss log n) tests for all positive integers n which matches the upper bound on the number of tests when all positive subsets are singletons, i.e. s = 1. (2) All tests in our algorithm can have the same number of tested items k. Thus, our algorithm can solve the problem with additional constraints on the number of tested items in each test, such as maximum or minimum number of tested items. © 2011 Springer-Verlag.en_HK
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science)en_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectcombinatorial group testingen_HK
dc.subjectknock-out studyen_HK
dc.subjectpooling designen_HK
dc.titleNon-adaptive complex group testing with multiple positive setsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.emailLeung, HCM:cmleung2@cs.hku.hken_HK
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityLeung, HCM=rp00144en_HK
dc.identifier.authorityYiu, SM=rp00207en_HK
dc.description.naturepostprint-
dc.identifier.doi10.1007/978-3-642-20877-5_19en_HK
dc.identifier.scopuseid_2-s2.0-79955783521en_HK
dc.identifier.hkuros187797en_US
dc.identifier.hkuros208234-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79955783521&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6648 LNCSen_HK
dc.identifier.spage172en_HK
dc.identifier.epage183en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Tokyo, Japan, 23-25 May 2011. In Lecture Notes in Computer Science, 2011, v. 6648, p. 172-183-
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridLeung, HCM=35233742700en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK
dc.customcontrol.immutablesml 151014-