{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T12:27:13Z","timestamp":1770294433363,"version":"3.49.0"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["MOST107-2218-E-194-015-MY3"],"award-info":[{"award-number":["MOST107-2218-E-194-015-MY3"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["MOST108-2221-E-194-026-MY3"],"award-info":[{"award-number":["MOST108-2221-E-194-026-MY3"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s00453-021-00885-w","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T07:02:57Z","timestamp":1635404577000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Approximation Algorithm for Vertex Cover with Multiple Covering Constraints"],"prefix":"10.1007","volume":"84","author":[{"given":"Eunpyeong","family":"Hung","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7238-3093","authenticated-orcid":false,"given":"Mong-Jen","family":"Kao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"issue":"2","key":"885_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jagm.2000.1150","volume":"39","author":"R Bar-Yehuda","year":"2001","unstructured":"Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2), 137\u2013144 (2001)","journal-title":"J. Algorithms"},{"key":"885_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2014.04.006","volume":"555","author":"SK Bera","year":"2014","unstructured":"Bera, S.K., Gupta, S., Kumar, A., Roy, S.: Approximation algorithms for the partition vertex cover problem. Theor. Comput. Sci. 555, 2\u20138 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"885_CR3","doi-asserted-by":"crossref","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 In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pages 298\u2013308. Springer, 1998","DOI":"10.1007\/BFb0028569"},{"issue":"2","key":"885_CR4","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1137\/S0097539703422479","volume":"36","author":"J Chuzhoy","year":"2006","unstructured":"Chuzhoy, J.: Covering problems with hard capacities. SIAM J. Comput. 36(2), 498\u2013515 (2006)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"885_CR5","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0167-6377(99)00045-0","volume":"25","author":"T Fujito","year":"1999","unstructured":"Fujito, T.: On approximation of the submodular set cover problem. Oper. Res. Lett. 25(4), 169\u2013174 (1999)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"885_CR6","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 53(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"key":"885_CR7","doi-asserted-by":"crossref","unstructured":"Hochbaum, D. S.: The t-vertex cover problem: Extending the half integrality framework with budget constraints. In Approximation Algorithms for Combinatorial Optimization, International Workshop APPROX\u201998, Aalborg, Denmark, July 18-19, 1998, Proceedings, volume 1444, pages 111\u2013122. Springer, 1998","DOI":"10.1007\/BFb0053968"},{"issue":"3","key":"885_CR8","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"885_CR9","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 55(1), 227\u2013239 (2009)","journal-title":"Algorithmica"},{"key":"885_CR10","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin, Heidelberg (2001)"},{"issue":"4","key":"885_CR11","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00885-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00885-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00885-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T14:06:27Z","timestamp":1643033187000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00885-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["885"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00885-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,28]]},"assertion":[{"value":"8 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}