{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T20:30:45Z","timestamp":1649190645107},"reference-count":8,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2018,5,30]],"date-time":"2018-05-30T00:00:00Z","timestamp":1527638400000},"content-version":"vor","delay-in-days":149,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2017,10,30]]},"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We propose and analyze a simple <jats:italic>purely combinatorial algorithm<\/jats:italic> for <jats:sc>max <jats:italic>k<\/jats:italic>-vertex cover<\/jats:sc> in bipartite graphs, achieving approximation ratio\u00a00.7. The only combinatorial algorithm currently known until now for this problem is the natural greedy algorithm, that achieves ratio (<jats:italic>e <\/jats:italic>\u2212 1)\/<jats:italic>e<\/jats:italic> = 0.632.<\/jats:p>","DOI":"10.1051\/ro\/2017085","type":"journal-article","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T07:39:38Z","timestamp":1509521978000},"page":"305-314","source":"Crossref","is-referenced-by-count":1,"title":["Combinatorial approximation of maximum <i>k<\/i>-vertex cover in bipartite graphs within ratio\u00a00.7"],"prefix":"10.1051","volume":"52","author":[{"given":"Vangelis Th.","family":"Paschos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2018,5,30]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Ageev A.A. and \nSviridenko M., Approximation algorithms for maximum coverage and max cut with given sizes of parts, in \nProc. Conference on Integer Programming and Combinatorial Optimization, IPCO\u201999, edited by \nCornu\u00e9jols G., \nBurkard R.E. and \nWoeginger G.J.. Vol. 1610 of Lecture Notes in Computer Science. \nSpringer-Verlag \n(1999) 17\u201330.","DOI":"10.1007\/3-540-48777-8_2"},{"key":"R2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.dam.2013.05.015","volume":"165","author":"Apollonio","year":"2014","journal-title":"Discrete Appl. Math."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A., \nKleinberg R. and \nLee H., Approximating low-dimensional coverage problems, in \nProc. Symposuim on Computational Geometry, SoCG\u201912, edited by \nDey T.K. and \nWhitesides S.. \nACM, \nChapel Hill, NC \n(2012) 161\u2013170.","DOI":"10.1145\/2261250.2261274"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Caskurlu B., \nMkrtchyan V., \nParekh O. and \nSubramani K., On partial vertex cover and budgeted maximum coverage problems in bipartite graphs, in \nProc. Theoretical Computer Science, IFIP TC 1\/WG 2.2 International Conference, TCS\u201914, edited by \nDiaz J., \nLanese I. and \nSangiorgi D.. Vol. 8705 of Lecture Notes in Computer Science. \nSpringer-Verlag \n(2014) 13\u201326.","DOI":"10.1007\/978-3-662-44602-7_2"},{"key":"R5","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"Cornuejols","year":"1977","journal-title":"Manag. Sci."},{"key":"R6","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1002\/(SICI)1520-6750(199809)45:6<615::AID-NAV5>3.0.CO;2-5","volume":"45","author":"Hochbaum","year":"1998","journal-title":"Naval Res. Logist."},{"key":"R7","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"Petrank","year":"1994","journal-title":"Comput. Complex."},{"key":"R8","unstructured":"Trevisan L., Max cut and the smallest eigenvalue, in \nProc. STOC\u201909 \n(2009) 263\u2013272."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2017085\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T07:36:51Z","timestamp":1584689811000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2017085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":8,"journal-issue":{"issue":"1"},"alternative-id":["ro170157"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2017085","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}