{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T06:27:48Z","timestamp":1780554468206,"version":"3.54.1"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1984,10,1]],"date-time":"1984-10-01T00:00:00Z","timestamp":465436800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1984,10]]},"DOI":"10.1007\/bf01874392","type":"journal-article","created":{"date-parts":[[2005,7,2]],"date-time":"2005-07-02T18:31:47Z","timestamp":1120329107000},"page":"255-271","source":"Crossref","is-referenced-by-count":20,"title":["A probabilistic analysis of the set covering problem"],"prefix":"10.1007","volume":"1","author":[{"given":"Carlo","family":"Vercellis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01874392_CR1","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R. Bar-Yehuda","year":"1981","unstructured":"R. Bar-Yehuda and S. Even, A linear time approximation algorithm for the weighted vertex cover problem. J. of Algorithms 2(1981)198.","journal-title":"J. of Algorithms"},{"key":"BF01874392_CR2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"V. Chv\u00e1tal, A greedy heuristic for the set covering problem, Math. Oper. Res. 4(1979)233.","journal-title":"Math. Oper. Res."},{"key":"BF01874392_CR3","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D.S. Hochbaum","year":"1982","unstructured":"D.S. Hochbaum, Approximation algorithm for the set covering and vertex cover problems, SIAM J. Comput. 11(1982)555.","journal-title":"SIAM J. Comput."},{"key":"BF01874392_CR4","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"D.S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. System Sci. 9(1974)256.","journal-title":"J. Comput. System Sci."},{"key":"BF01874392_CR5","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, ed. R.E. Miller and J.W. Thatcher (Plenum Press, New York, 1972) p. 85."},{"key":"BF01874392_CR6","first-page":"1","volume-title":"Algorithms and Complexity","author":"R.M. Karp","year":"1976","unstructured":"R.M. Karp, The probabilistic analysis of some combinatorial search algorithms, in: Algorithms and Complexity, ed. J.F. Traub (Academic Press, New York, 1976) p. 1."},{"key":"BF01874392_CR7","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lovasz","year":"1975","unstructured":"L. Lovasz, On the ratio of optimal integral and fractional covers, Discr. Math. 13(1975)383.","journal-title":"Discr. Math."},{"key":"BF01874392_CR8","volume-title":"Integer Programming","author":"H.M. Salkin","year":"1975","unstructured":"H.M. Salkin, Integer Programming (Addison-Wesley, Reading, 1975)."},{"key":"BF01874392_CR9","unstructured":"B.W. Weide, Statistical methods in algorithm design and analysis, Ph. D. Thesis, Carnegie-Mellon University (1978)."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01874392.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01874392\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01874392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T14:56:45Z","timestamp":1557500205000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01874392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,10]]},"references-count":9,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1984,10]]}},"alternative-id":["BF01874392"],"URL":"https:\/\/doi.org\/10.1007\/bf01874392","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1984,10]]}}}