{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:09Z","timestamp":1759639089310},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642360640"},{"type":"electronic","value":"9783642360657"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36065-7_14","type":"book-chapter","created":{"date-parts":[[2013,1,21]],"date-time":"2013-01-21T11:36:53Z","timestamp":1358768213000},"page":"137-145","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for the Partition Vertex Cover Problem"],"prefix":"10.1007","author":[{"given":"Suman Kalyan","family":"Bera","sequence":"first","affiliation":[]},{"given":"Shalmoli","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[]},{"given":"Sambuddha","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","volume-title":"Approximation algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer-Verlag New York, Inc., New York (2001)"},{"doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press (2010)","key":"14_CR2","DOI":"10.1017\/CBO9780511921735"},{"doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Even, S.: A linear time approximation algorithm for approximating the weighted vertex cover (1981)","key":"14_CR3","DOI":"10.1016\/0196-6774(81)90020-1"},{"volume-title":"Approximation algorithms for NP-hard problems","year":"1997","unstructured":"Hochbaum, D.S. (ed.): Approximation algorithms for NP-hard problems. PWS Publishing Co., Boston (1997)","key":"14_CR4"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/BFb0028569","volume-title":"STACS 98","author":"N.H. Bshouty","year":"1998","unstructured":"Bshouty, N.H., Burroughs, L.: Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 298\u2013308. Springer, Heidelberg (1998)"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BFb0053968","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"D.S. Hochbaum","year":"1998","unstructured":"Hochbaum, D.S.: The t-Vertex Cover Problem: Extending the Half Integrality Framework with Budget Constraints. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol.\u00a01444, pp. 111\u2013122. Springer, Heidelberg (1998)"},{"key":"14_CR7","first-page":"71","volume-title":"Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999","author":"R. Bar-Yehuda","year":"1999","unstructured":"Bar-Yehuda, R.: Using homogenous weights for approximating the partial cover problem. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999, pp. 71\u201375. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"issue":"1","key":"14_CR8","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R. Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms\u00a053(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"key":"14_CR9","first-page":"106","volume-title":"Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000","author":"R.D. Carr","year":"2000","unstructured":"Carr, R.D., Fleischer, L.K., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000, pp. 106\u2013115. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"unstructured":"Kearns, M.J.: The computational complexity of machine learning (1990)","key":"14_CR10"},{"issue":"5","key":"14_CR11","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P. Slav\u00edk","year":"1997","unstructured":"Slav\u00edk, P.: Improved performance of the greedy algorithm for partial cover. Inf. Process. Lett.\u00a064(5), 251\u2013254 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"14_CR12","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s00453-007-9003-z","volume":"55","author":"J. Mestre","year":"2009","unstructured":"Mestre, J.: A primal-dual approximation algorithm for partial vertex cover: Making educated guesses. Algorithmica\u00a055(1), 227\u2013239 (2009)","journal-title":"Algorithmica"},{"key":"14_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-540-75520-3_31","volume-title":"Algorithms \u2013 ESA 2007","author":"R. Bar-Yehuda","year":"2007","unstructured":"Bar-Yehuda, R., Flysher, G., Mestre, J., Rawitz, D.: Approximation of Partial Capacitated Vertex Cover. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 335\u2013346. Springer, Heidelberg (2007)"},{"key":"14_CR14","first-page":"642","volume-title":"Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2001","author":"M. Charikar","year":"2001","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2001, pp. 642\u2013651. Society for Industrial and Applied Mathematics, Philadelphia (2001)"},{"key":"14_CR15","first-page":"826","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008","author":"K. Chen","year":"2008","unstructured":"Chen, K.: A constant factor approximation algorithm for k-median clustering with outliers. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 826\u2013835. Society for Industrial and Applied Mathematics, Philadelphia (2008)"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1145\/1060590.1060650","volume-title":"Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2005","author":"N. Garg","year":"2005","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-mst problem in graphs. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 396\u2013402. ACM, New York (2005)"},{"key":"14_CR17","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1145\/1109557.1109625","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2006","author":"D. Golovin","year":"2006","unstructured":"Golovin, D., Nagarajan, V., Singh, M.: Approximating the k-multicut problem. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2006, pp. 621\u2013630. ACM, New York (2006)"},{"doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J., Chekuri, C., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: STOC, pp. 783\u2013792 (2011)","key":"14_CR18","DOI":"10.1145\/1993636.1993740"},{"issue":"6","key":"14_CR19","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G. C\u0103linescu","year":"2011","unstructured":"C\u0103linescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput.\u00a040(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"14_CR20","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"14_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-540-68891-4_20","volume-title":"Integer Programming and Combinatorial Optimization","author":"T. Carnes","year":"2008","unstructured":"Carnes, T., Shmoys, D.: Primal-Dual Schema for Capacitated Covering Problems. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 288\u2013302. Springer, Heidelberg (2008)"},{"unstructured":"Hochbaum, D.S.: Approximation algorithm for the weighted set covering and node cover problems (1980) (unpublished manuscript)","key":"14_CR22"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36065-7_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T09:34:52Z","timestamp":1620120892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36065-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642360640","9783642360657"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36065-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}