Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783642208775_19
 Scopus: eid_2s2.079955783521
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Nonadaptive complex group testing with multiple positive sets
Title  Nonadaptive complex group testing with multiple positive sets 

Authors  
Keywords  combinatorial group testing knockout study nonadaptive complex group testing pooling design 
Issue Date  2011 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Tokyo, Japan, 2325 May 2011. In Lecture Notes in Computer Science, 2011, v. 6648, p. 172183 How to Cite? 
Abstract  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 nonadaptive 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 wellstudied 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 nonadaptive 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 SpringerVerlag. 
Description  LNCS v. 6648 is conference proceedings of TAMC 2011 
Persistent Identifier  http://hdl.handle.net/10722/135706 
ISSN  2005 Impact Factor: 0.302 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Chin, FYL  en_HK 
dc.contributor.author  Leung, HCM  en_HK 
dc.contributor.author  Yiu, SM  en_HK 
dc.date.accessioned  20110727T01:47:00Z   
dc.date.available  20110727T01:47:00Z   
dc.date.issued  2011  en_HK 
dc.identifier.citation  The 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Tokyo, Japan, 2325 May 2011. In Lecture Notes in Computer Science, 2011, v. 6648, p. 172183  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/135706   
dc.description  LNCS v. 6648 is conference proceedings of TAMC 2011   
dc.description.abstract  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 nonadaptive 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 wellstudied 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 nonadaptive 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 SpringerVerlag.  en_HK 
dc.language  eng  en_US 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science)  en_HK 
dc.rights  The original publication is available at www.springerlink.com   
dc.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
dc.subject  combinatorial group testing  en_HK 
dc.subject  knockout study  en_HK 
dc.subject  nonadaptive complex group testing  en_HK 
dc.subject  pooling design  en_HK 
dc.title  Nonadaptive complex group testing with multiple positive sets  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.email  Chin, FYL:chin@cs.hku.hk  en_HK 
dc.identifier.email  Leung, HCM:cmleung2@cs.hku.hk  en_HK 
dc.identifier.email  Yiu, SM:smyiu@cs.hku.hk  en_HK 
dc.identifier.authority  Chin, FYL=rp00105  en_HK 
dc.identifier.authority  Leung, HCM=rp00144  en_HK 
dc.identifier.authority  Yiu, SM=rp00207  en_HK 
dc.description.nature  postprint   
dc.identifier.doi  10.1007/9783642208775_19  en_HK 
dc.identifier.scopus  eid_2s2.079955783521  en_HK 
dc.identifier.hkuros  187797  en_US 
dc.identifier.hkuros  208234   
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.079955783521&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  6648 LNCS  en_HK 
dc.identifier.spage  172  en_HK 
dc.identifier.epage  183  en_HK 
dc.publisher.place  Germany  en_HK 
dc.description.other  The 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Tokyo, Japan, 2325 May 2011. In Lecture Notes in Computer Science, 2011, v. 6648, p. 172183   
dc.identifier.scopusauthorid  Chin, FYL=7005101915  en_HK 
dc.identifier.scopusauthorid  Leung, HCM=35233742700  en_HK 
dc.identifier.scopusauthorid  Yiu, SM=7003282240  en_HK 
dc.customcontrol.immutable  sml 151014   