{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T02:43:59Z","timestamp":1780627439169,"version":"3.54.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T00:00:00Z","timestamp":1666396800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T00:00:00Z","timestamp":1666396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s11704-022-1665-9","type":"journal-article","created":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T10:02:53Z","timestamp":1666432973000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties"],"prefix":"10.1007","volume":"17","author":[{"given":"Xiaofei","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jinhua","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,10,22]]},"reference":[{"key":"1665_CR1","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R M Karp","year":"1972","unstructured":"Karp R M. Reducibility among combinatorial problems. In: Miller R E, Thatcher J W, Bohlinger J D, eds. Complexity of Computer Computations. Boston: Springer, 1972, 85\u2013103"},{"key":"1665_CR2","volume-title":"Approximation Algorithms","author":"V V Vazirani","year":"2001","unstructured":"Vazirani V V. Approximation Algorithms. Berlin, Heidelberg: Springer, 2001"},{"issue":"3","key":"1665_CR3","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-\u03b5. Journal of Computer and System Sciences, 2008, 74(3): 335\u2013349","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"1665_CR4","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D S Hochbaum","year":"1982","unstructured":"Hochbaum D S. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 1982, 11(3): 555\u2013556","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"1665_CR5","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda R, Even S. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 1981, 2(2): 198\u2013203","journal-title":"Journal of Algorithms"},{"key":"1665_CR6","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: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science. 1998, 298\u2013308","DOI":"10.1007\/BFb0028569"},{"key":"1665_CR7","doi-asserted-by":"crossref","unstructured":"Hochbaum D S. The t-vertex cover problem: extending the half integrality framework with budget constraints. In: Proceedings of International Workshop on Approximation Algorithms for Combinatorial Optimization. 1998, 111\u2013122","DOI":"10.1007\/BFb0053968"},{"issue":"2","key":"1665_CR8","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. Journal of Algorithms, 2001, 39(2): 137\u2013144","journal-title":"Journal of Algorithms"},{"issue":"1","key":"1665_CR9","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. Journal of Algorithms, 2004, 53(1): 55\u201384","journal-title":"Journal of Algorithms"},{"issue":"1","key":"1665_CR10","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, 2009, 55(1): 227\u2013239","journal-title":"Algorithmica"},{"issue":"2","key":"1665_CR11","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0377-2217(02)00071-1","volume":"140","author":"D S Hochbaum","year":"2002","unstructured":"Hochbaum D S. Solving integer programs over monotone inequalities in three variables: a framework for half integrality and good approximations. European Journal of Operational Research, 2002, 140(2): 291\u2013321","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"1665_CR12","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/050625382","volume":"19","author":"R Bar-Yehuda","year":"2005","unstructured":"Bar-Yehuda R, Rawitz D. On the equivalence between the primal-dual schema and the local ratio technique. SIAM Journal on Discrete Mathematics, 2005, 19(3): 762\u2013797","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"1665_CR13","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/s00453-014-9911-7","volume":"73","author":"Y Li","year":"2015","unstructured":"Li Y, Du D, Xiu N, Xu D. Improved approximation algorithms for the facility location problems with linear\/submodular penalties. Algorithmica, 2015, 73(2): 460\u2013482","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"1665_CR14","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s00453-011-9526-1","volume":"63","author":"D Du","year":"2012","unstructured":"Du D, Lu R, Xu D. A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica, 2012, 63(1\u20132): 191\u2013200","journal-title":"Algorithmica"},{"issue":"6","key":"1665_CR15","doi-asserted-by":"publisher","first-page":"2165","DOI":"10.1007\/s11590-021-01724-1","volume":"15","author":"X Liu","year":"2021","unstructured":"Liu X, Li W. Approximation algorithms for the multiprocessor scheduling with submodular penalties. Optimization Letters, 2021, 15(6): 2165\u20132180","journal-title":"Optimization Letters"},{"key":"1665_CR16","doi-asserted-by":"publisher","unstructured":"Liu X, Li W, Xie R. A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem. Optimization Letters, 2021, DOI: https:\/\/doi.org\/10.1007\/s11590-021-01831-z","DOI":"10.1007\/s11590-021-01831-z"},{"key":"1665_CR17","doi-asserted-by":"crossref","unstructured":"Iwata S, Nagano K. Submodular function minimization under covering constraints. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science. 2009, 671\u2013680","DOI":"10.1109\/FOCS.2009.31"},{"key":"1665_CR18","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2016.04.005","volume":"630","author":"D Xu","year":"2016","unstructured":"Xu D, Wang F, Du D, Wu C. Approximation algorithms for submodular vertex cover problems with linear\/submodular penalties using primal-dual technique. Theoretical Computer Science, 2016, 630: 117\u2013125","journal-title":"Theoretical Computer Science"},{"key":"1665_CR19","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2016.10.017","volume":"659","author":"N Kamiyama","year":"2017","unstructured":"Kamiyama N. A note on the submodular vertex cover problem with submodular penalties. Theoretical Computer Science, 2017, 659: 95\u201397","journal-title":"Theoretical Computer Science"},{"key":"1665_CR20","doi-asserted-by":"publisher","unstructured":"Guo J S, Liu W, Hou B. An approximation algorithm for p-prize-collecting set cover problem. Journal of the Operations Research Society of China, 2021, DOI: https:\/\/doi.org\/10.1007\/s40305-021-00364-7","DOI":"10.1007\/s40305-021-00364-7"},{"issue":"2","key":"1665_CR21","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0166-218X(02)00458-4","volume":"131","author":"L Fleischer","year":"2003","unstructured":"Fleischer L, Iwata S. A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Applied Mathematics, 2003, 131(2): 311\u2013322","journal-title":"Discrete Applied Mathematics"},{"key":"1665_CR22","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2019.01.027","volume":"778","author":"M J Kao","year":"2019","unstructured":"Kao M J, Shiau J Y, Lin C C, Lee D T. Tight approximation for partial vertex cover with hard capacities. Theoretical Computer Science, 2019, 778: 61\u201372","journal-title":"Theoretical Computer Science"},{"key":"1665_CR23","doi-asserted-by":"crossref","unstructured":"Cheung W C, Goemans M X, Wong S C W. Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. 2014, 1714\u20131726","DOI":"10.1137\/1.9781611973402.124"},{"key":"1665_CR24","doi-asserted-by":"crossref","unstructured":"Wong S C W. Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. 2017, 2626\u20132637","DOI":"10.1137\/1.9781611974782.173"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-022-1665-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-022-1665-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-022-1665-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T20:29:30Z","timestamp":1721420970000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-022-1665-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,22]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1665"],"URL":"https:\/\/doi.org\/10.1007\/s11704-022-1665-9","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,22]]},"assertion":[{"value":"23 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"173404"}}