An Almost Optimal Algorithm for Generalized Threshold Group Testing with Inhibitors
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
864 | en_US |
dc.citation.issue |
6 | en_US |
dc.citation.spage |
851 | en_US |
dc.citation.volume |
18 | en_US |
dc.citation.woscount |
3 | |
dc.contributor.author |
Chen, Hong-Bin | en_US |
dc.contributor.author |
De Bonis, Annalisa | en_US |
dc.contributor.department |
應用數學系 | zh_TW |
dc.contributor.department |
Department of Applied Mathematics | en_US |
dc.date.accessioned |
2014-12-08T15:33:47Z | |
dc.date.available |
2014-12-08T15:33:47Z | |
dc.date.issued |
2011-06-01 | en_US |
dc.description.abstract |
Group testing is a search paradigm where one is given a population S of n elements and an unknown subset P subset of S of defective elements and the goal is to determine P by performing tests on subsets of S. In classical group testing a test on a subset Q subset of S receives a YES response if vertical bar Q boolean AND P vertical bar >= 1, and a NO response otherwise. In group testing with inhibitors (GTI), identifying the defective items is more difficult due to the presence of elements called inhibitors that interfere with the queries so that the answer to a query is YES if and only if the queried group contains at least one defective item and no inhibitor. In the present article, we consider a new generalization of the GTI model in which there are two unknown thresholds h and g and the response to a test is YES both in the case when the queried subset contains at least one defective item and less than h inhibitors, and in the case when the queried subset contains at least g defective items. Moreover, our search model assumes that no knowledge on the number vertical bar P vertical bar of defective items is given. We derive lower bounds on the minimum number of tests required to determine the defective items under this model and present an algorithm that uses an almost optimal number of tests. | en_US |
dc.identifier.doi |
10.1089/cmb.2010.0030 | en_US |
dc.identifier.issn |
1066-5277 | en_US |
dc.identifier.journal |
JOURNAL OF COMPUTATIONAL BIOLOGY | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1089/cmb.2010.0030 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/23345 | |
dc.identifier.wosnumber |
WOS:000291016200007 | |
dc.language.iso |
en_US | en_US |
dc.subject |
algorithms | en_US |
dc.subject |
group testing | en_US |
dc.subject |
inhibitors | en_US |
dc.subject |
superimposed codes | en_US |
dc.title |
An Almost Optimal Algorithm for Generalized Threshold Group Testing with Inhibitors | en_US |
dc.type |
Article | en_US |
檔案
- 000291016200007.pdf (362.2 KB, Adobe PDF)
所屬典藏: 期刊論文
引用此條目
Chen, H.-B., & De Bonis, A. (2011). An Almost Optimal Algorithm for Generalized Threshold Group Testing with Inhibitors. JOURNAL OF COMPUTATIONAL BIOLOGY, 18(6), 851–864. https://doi.org/10.1089/cmb.2010.0030
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/23345