Show simple item record

dc.contributor.authorCheng, Yongxien_US
dc.contributor.authorDu, Dingzhuen_US
dc.contributor.authorXu, Yinfengen_US
dc.date.accessioned2014-11-19T22:09:54Z
dc.date.available2015-04-23en_US
dc.date.available2014-11-19T22:09:54Z
dc.date.created2014-04-23en_US
dc.identifier.citationCheng, Yongxi, Ding-Zhu Du, and Yinfeng Xu. 2014. "A Zig-Zag Approach for Competitive Group Testing." Informs Journal on Computing 26(4): 677-689.en_US
dc.identifier.issn1091-9856en_US
dc.identifier.urihttp://hdl.handle.net/10735.1/4210
dc.description.abstractIn 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² 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 < ρ₀ where ρ₀ = 1 − 4/e² = 0.45..., 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.en_US
dc.description.sponsorshipNational Natural Science Foundation of China (Grants 11101326, 71071123), and the Program for Changjiang Scholars and Innovative Research Team in University (IRT1173).en_US
dc.relation.urihttp://dx.doi.org/10.1287/ijoc.2014.0591en_US
dc.rights©2014 INFORMSen_US
dc.subjectAlgorithmsen_US
dc.subjectGroup testingen_US
dc.subjectFault-detection problemsen_US
dc.titleA Zig-Zag Approach for Competitive Group Testingen_US
dc.type.genrearticleen_US
dc.source.journalINFORMS Journal on Computingen_US
dc.identifier.volume26en_US
dc.identifier.issue4en_US
dc.contributor.ISNI0000 0001 0891 4462 (Du, D)en_US
dc.contributor.LCNA88207689 (Du, D)en_US
dc.contributor.VIAF288884264 (Du, D)en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record