{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:00:57Z","timestamp":1787504457251,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540404934","type":"print"},{"value":"9783540450610","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_15","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:04Z","timestamp":1184586844000},"page":"164-175","source":"Crossref","is-referenced-by-count":9,"title":["An Improved Approximation Algorithm for Vertex Cover with Hard Capacities"],"prefix":"10.1007","author":[{"given":"Rajiv","family":"Gandhi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eran","family":"Halperin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"15_CR1","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"R. Bar-Yehuda and S. Even. A Local-Ratio Theorem for Approximating The Weighted Vertex Cover Problem. Annals of Discrete Mathematics, 25:27\u201345, 1985.","journal-title":"Annals of Discrete Mathematics"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0304-3975(99)00130-9","volume":"250","author":"J. Bar-Ilan","year":"2001","unstructured":"J. Bar-Ilan, G. Kortsarz and D. Peleg. Generalized submodular cover problems and applications. Theoretical Computer Science, 250, pages 179\u2013200, 2001.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"15_CR3","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. Mathematics of Operations Research, vol. 4, No 3, pages 233\u2013235, 1979.","journal-title":"Mathematics of Operations Research"},{"key":"15_CR4","unstructured":"R. D. Carr, L. K. Fleischer, V. J. Leung and C. A. Phillips. Strengthening Integrality Gaps For Capacitated Network Design and Covering Problems. In Proc. of the 11th ACM-SIAM Symposium on Discrete Algorithms, pages 106\u2013115, 2000."},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy and J. Naor. Covering Problems with Hard Capacities. Proc. of the Forty-Third IEEE Symp. on Foundations of Computer Science, 481\u2013489, 2002.","DOI":"10.1109\/SFCS.2002.1181972"},{"issue":"4","key":"15_CR6","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1287\/moor.7.4.515","volume":"7","author":"G. Dobson","year":"1980","unstructured":"G. Dobson. Worst Case Analysis of Greedy Heuristics For Integer Programming with Non-Negative Data. Math. of Operations Research, 7(4):515\u2013531, 1980.","journal-title":"Math. of Operations Research"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"R. Gandhi, S. Khuller, S. Parthasarathy and A. Srinivasan. Dependent Rounding in Bipartite Graphs. In Proc. of the Forty-Third IEEE Symposium on Foundations of Computer Science, pages 323\u2013332, 2002.","DOI":"10.1109\/SFCS.2002.1181955"},{"key":"15_CR8","unstructured":"S. Guha, R. Hassin, S. Khuller and E. Or. Capacitated Vertex Covering with Applications. Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 858\u2013865, 2002."},{"key":"15_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":"D. S. Johnson, Approximation algorithms for combinatorial problems. J. Computer and System Sciences, 9, pages 256\u2013278, 1974.","journal-title":"J. Computer and System Sciences"},{"key":"15_CR10","unstructured":"E. Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, pages 329\u2013337, 2000."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D. S. Hochbaum","year":"1982","unstructured":"D. S. Hochbaum. Approximation Algorithms for the Set Covering and Vertex Cover Problems. SIAM Journal on Computing, 11:555\u2013556, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"D. S. Hochbaum","year":"1982","unstructured":"D. S. Hochbaum. Heuristics for the fixed cost median problem. Mathematical Programming, 22:148\u2013162, 1982.","journal-title":"Mathematical Programming"},{"key":"15_CR13","unstructured":"D. S. Hochbaum (editor). Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1996."},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"S. G. Kolliopoulos and N. E. Young. Tight Approximation Results for General Covering Integer Programs. In Proc. of the Forty-Second Annual Symposium on Foundations of Computer Science, pages 522\u2013528, 2001.","DOI":"10.1109\/SFCS.2001.959928"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz, On the ratio of optimal integral and fractional covers. Discrete Math., 13, pages 383\u2013390, 1975.","journal-title":"Discrete Math."},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"M. P\u00e1l, \u00c9. Tardos and T. Wexler. Facility Location with Nonuniform Hard Capacities. In Proc. Forty-Second Annual Symposium on Foundations of Computer Science, 329\u2013338, 2001.","DOI":"10.1109\/SFCS.2001.959907"},{"key":"15_CR17","unstructured":"V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001."},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L. A. Wolsey","year":"1982","unstructured":"L. A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2:385\u2013393, 1982.","journal-title":"Combinatorica"},{"key":"15_CR19","unstructured":"N. E. Young. K-medians, facility location, and the Chernoff-Wald bound. ACM-SIAM Symposium on Discrete Algorithms, pages 86\u201395, 2000."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T23:14:34Z","timestamp":1556666074000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}