{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:53:51Z","timestamp":1787500431891,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540441861","type":"print"},{"value":"9783540457534","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45753-4_15","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T07:37:09Z","timestamp":1187249829000},"page":"161-174","source":"Crossref","is-referenced-by-count":17,"title":["Improved Approximation Algorithms for the Partial Vertex Cover Problem"],"prefix":"10.1007","author":[{"given":"Eran","family":"Halperin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"key":"15_CR1","unstructured":"R. Bar-Yehuda.Using homogeneous weights for approximating the partial cover problem.In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, pages 71\u201375,1999."},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"N. Bshouty and L. Burroughs. Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In Fifteenth Annual Symposium on the Theoretical Aspects of Computer Science, pages 298\u2013308,1998.","DOI":"10.1007\/BFb0028569"},{"key":"15_CR3","volume-title":"An Introduction to Probability Theory and its Applications","author":"W. Feller","year":"1968","unstructured":"W. Feller. An Introduction to Probability Theory and its Applications. John Wiley & Sons, New York,3 edition,1968.","edition":"3 edition"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"R. Gandhi, S. Khuller, and A. Srinivasan. Approximation algorithms for partial covering problems.In Proceedings of the 28th International Colloquium on Automata, Languages and Programming,Crete, Greece, pages 225\u2013236, 2001.","DOI":"10.1007\/3-540-48224-5_19"},{"key":"15_CR5","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_CR6","unstructured":"E. Halperin, R. Nathaniel, and U. Zwick. Coloring k-colorable graphs using smaller palettes. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms,Washington, D.C.,pages 319\u2013326,2001."},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"D.S. Hochbaum.The t-vertex cover problem:Extending the half integrality framework with budget constraints. In First International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 111\u2013122,1998.","DOI":"10.1007\/BFb0053968"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming.Journal of the ACM,45: 246\u2013265,1998.","journal-title":"Journal of the ACM"},{"key":"15_CR9","volume-title":"Probability Theory","author":"A. R\u00e9nyi","year":"1970","unstructured":"A. R\u00e9nyi. Probability Theory.Elsevier\/North-Holland, Amsterdam, London, New York,1970."},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"A. Srinivasan.Distributions on level-sets with applications to approximation algorithms.In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science,Las Vegas, Nevada, pages 588\u2013597,2001.","DOI":"10.1109\/SFCS.2001.959935"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45753-4_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T22:34:27Z","timestamp":1550788467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45753-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441861","9783540457534"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-45753-4_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}