{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T04:35:53Z","timestamp":1778646953298,"version":"3.51.4"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p> Suppose that we are given a set of n elements d of which have a property called defective. A group test can check for any subset, called a pool, whether it contains a defective. It is known that a nearly optimal number of O(d log (n\/d)) pools in two stages (where tests within a stage are done in parallel) are sufficient, but then the searcher must know d in advance. Here we explore group testing strategies that use a nearly optimal number of pools and a few stages although d is not known beforehand. We prove a lower bound of \u03a9( log d\/ log log d) stages and more general pools versus stages tradeoff. This is almost tight, since O( log d) stages are sufficient for a strategy with O(d log n) pools. As opposed to this negative result, we devise a randomized strategy using O(d log (n\/d)) pools in three stages, with any desired success probability 1-\u03f5. With some additional measures even two stages are enough. Open questions concern the optimal constant factors and practical implications. A related problem motivated by biological network analysis is to learn hidden vertex covers of a small size k in unknown graphs by edge group tests. (Does a given subset of vertices contain an edge?) We give a one-stage strategy using O(k<jats:sup>3<\/jats:sup> log n) pools, with any parameterized algorithm for vertex cover enumeration as a decoder. During the course of this work we also provide a classification of types of randomized search strategies in general. <\/jats:p>","DOI":"10.1142\/s179383091000067x","type":"journal-article","created":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T08:44:00Z","timestamp":1286873040000},"page":"291-311","source":"Crossref","is-referenced-by-count":30,"title":["COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY"],"prefix":"10.1142","volume":"02","author":[{"given":"PETER","family":"DAMASCHKE","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Chalmers University, 41296 G\u00f6teborg, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"AZAM SHEIKH","family":"MUHAMMAD","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Chalmers University, 41296 G\u00f6teborg, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103431071"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.006"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00185-O"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-007-0070-5"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.10.009"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2007.0195"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061325"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00047-3"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.004"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703428002"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1142\/9789812773463"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793246690"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792227612"},{"key":"rf18","first-page":"7","volume":"18","author":"Dyachkov A. G.","journal-title":"Problems of Information Transmission"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1137\/050631847"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9087-z"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.854635"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1038\/nbt921"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(94)90067-1"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006649"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383091000067X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T01:34:39Z","timestamp":1565141679000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S179383091000067X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":20,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1142\/S179383091000067X"],"URL":"https:\/\/doi.org\/10.1142\/s179383091000067x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}