File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleNon-adaptive complex group testing with multiple positive sets
Authors
Keywordscombinatorial group testing
knock-out study
non-adaptive complex group testing
pooling design
Issue Date2011
PublisherSpringer 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, 23-25 May 2011. In Lecture Notes in Computer Science, 2011, v. 6648, p. 172-183 How to Cite?
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.
DescriptionLNCS v. 6648 is conference proceedings of TAMC 2011
Persistent Identifierhttp://hdl.handle.net/10722/135706
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

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.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectcombinatorial group testingen_HK
dc.subjectknock-out studyen_HK
dc.subjectnon-adaptive complex group testingen_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-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats