{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:05:41Z","timestamp":1742990741508,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_18","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T04:09:41Z","timestamp":1458533381000},"page":"235-248","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs"],"prefix":"10.1007","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[]},{"given":"Bruno","family":"Escoffier","sequence":"additional","affiliation":[]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[]},{"given":"Georgios","family":"Stamoulis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.dam.2013.05.015","volume":"165","author":"N Apollonio","year":"2014","unstructured":"Apollonio, N., Simeone, B.: The maximum vertex coverage problem on bipartite graphs. Discrete Appl. Math. 165, 37\u201348 (2014)","journal-title":"Discrete Appl. Math."},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-3-662-44602-7_2","volume-title":"Theoretical Computer Science","author":"B Caskurlu","year":"2014","unstructured":"Caskurlu, B., Mkrtchyan, V., Parekh, O., Subramani, K.: On partial vertex cover and budgeted maximum coverage problems in bipartite graphs. In: Diaz, J., Lanese, I., Sangiorgi, D. (eds.) TCS 2014. LNCS, vol. 8705, pp. 13\u201326. Springer, Heidelberg (2014)"},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1002\/(SICI)1520-6750(199809)45:6<615::AID-NAV5>3.0.CO;2-5","volume":"45","author":"DS Hochbaum","year":"1998","unstructured":"Hochbaum, D.S., Pathria, A.: Analysis of the greedy approach in problems of maximum \n                    \n                      \n                    \n                    $$k$$\n                  -coverage. Naval Res. Logistics 45, 615\u2013627 (1998)","journal-title":"Naval Res. Logistics"},{"key":"18_CR4","first-page":"161","volume-title":"Proceedings of Symposuim on Computational Geometry","author":"A Badanidiyuru","year":"2012","unstructured":"Badanidiyuru, A., Kleinberg, R., Lee, H.: Approximating low-dimensional coverage problems. In: Dey, T.K., Whitesides, S. (eds.) SoCG 2012, pp. 161\u2013170. ACM, Chapel Hill (2012)"},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/3-540-48777-8_2","volume-title":"Integer Programming and Combinatorial Optimization","author":"AA Ageev","year":"1999","unstructured":"Ageev, A.A., Sviridenko, M.I.: Approximation algorithms for maximum coverage and max cut with given sizes of parts. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol. 1610, p. 17. Springer, Heidelberg (1999)"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: gap location. Comput. Complex. 4, 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Bonnet, E., Escoffier, B., Paschos, V.T., Stamoulis, G.: A 0.821-ratio purely combinatorial algorithm for maximum \n                    \n                      \n                    \n                    $$k$$\n                  -vertex cover in bipartite graphs. CoRR \n                    arXiv:1409.6952v2\n                    \n                   (2015)","DOI":"10.1007\/978-3-662-49529-2_18"},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0196-6774(02)00005-6","volume":"43","author":"U Feige","year":"2002","unstructured":"Feige, U., Karpinski, M., Langberg, M.: Improved approximation of max-cut on graphs of bounded degree. J. Algorithms 43, 201\u2013219 (2002)","journal-title":"J. Algorithms"},{"key":"18_CR9","unstructured":"Abadie, J., Carpentier, J.: Generalization of the wolfe reduced gradient method to the case of non-linear constraints. In: Abadie, J., Carpentier, J. (eds.) Optimization. Academic Publishers (1969)"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logistics Q. 3, 95\u2013110 (1956)","journal-title":"Naval Res. Logistics Q."}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T17:29:22Z","timestamp":1559410162000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 March 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}