{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:57:01Z","timestamp":1725559021695},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_5","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T13:27:29Z","timestamp":1279027649000},"page":"39-50","source":"Crossref","is-referenced-by-count":2,"title":["Tight Approximability Results for Test Set Problems in Bioinformatics"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bhaskar","family":"DasGupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming-Yang","family":"Kao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"volume-title":"Complexity in Information Theory","year":"1986","key":"5_CR1","unstructured":"Abu-Mostafa, Y.S. (ed.): Complexity in Information Theory. Springer, Heidelberg (1986)"},{"issue":"1-3","key":"5_CR2","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/s10107-003-0414-6","volume":"98","author":"K.M.J. Bontridder De","year":"2003","unstructured":"De Bontridder, K.M.J., Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Hurkens, C.A.J., Lenstra, J.K., Ravi, R., Stougie, L.: Approximation algorithms for the test cover problem. Mathematical Programming-B\u00a098(1-3), 477\u2013491 (2003)","journal-title":"Mathematical Programming-B"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Borneman, J., Chrobak, M., Vedova, G.D., Figueroa, A., Jiang, T.: Probe Selection Algorithms with Applications in the Analysis of Microbial Communities. Bioinformatics\u00a017(suppl. 1) ,S39-S48 (2001)","DOI":"10.1093\/bioinformatics\/17.suppl_1.S39"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold for approximating set cover. JACM\u00a045, 634\u2013652 (1998)","journal-title":"JACM"},{"issue":"2","key":"5_CR5","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. Journal of Computer and System Sciences\u00a057(2), 187\u2013199 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR6","volume-title":"Computers and Intractability - A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability - A Guide to the Theory of NP-Completeness. W. H. Freeman & Co, New York (1979)"},{"key":"5_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees and Sequences. Cambridge University Press, Cambridge (1997)"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/3-540-44676-1_13","volume-title":"Algorithms - ESA 2001","author":"B.V. Halld\u00f3rsson","year":"2001","unstructured":"Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Ravi, R.: On the approximability of the minimum test collection problem. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 158\u2013169. Springer, Heidelberg (2001)"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation Algorithms for Combinatorial Problems, Journal of Computer and Systems Sciences\u00a09, 256\u2013278 (1974)","journal-title":"Journal of Computer and Systems Sciences"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Stoughton, R., Yeung, K.Y.: Algorithms for Choosing Differential Gene Expression Experiments. In: Proc. Third Annual International Conference on Computational Molecular Biology, pp. 208\u2013217 (1999)","DOI":"10.1145\/299432.299485"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lovasz","year":"1975","unstructured":"Lovasz, L.: On the Ratio of Optimal Integral and Fractional Covers. Discrete Mathematics\u00a013, 383\u2013390 (1975)","journal-title":"Discrete Mathematics"},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1137\/0906067","volume":"6","author":"B.M.E. Moret","year":"1985","unstructured":"Moret, B.M.E., Shapiro, H.D.: On minimizing a set of tests. SIAM Journal on Scientific and Statistical Computing\u00a06, 983\u20131003 (1985)","journal-title":"SIAM Journal on Scientific and Statistical Computing"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Rash, S., Gusfield, D.: String Barcoding: Uncovering Optimal Virus Signatures. In: Proc. Sixth Annual International Conference on Computational Molecular Biology, pp. 254\u2013261 (2002)","DOI":"10.1145\/565196.565229"},{"key":"5_CR14","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"C.E. Shannon","year":"1948","unstructured":"Shannon, C.E.: Mathematical Theory of Communication. Bell Systems Technical Journal\u00a027, 379\u2013423, 623-658 (1948)","journal-title":"Bell Systems Technical Journal"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T23:27:13Z","timestamp":1619998033000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}