{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,10]],"date-time":"2025-05-10T04:02:12Z","timestamp":1746849732178,"version":"3.40.5"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T00:00:00Z","timestamp":1728777600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T00:00:00Z","timestamp":1728777600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003787","name":"Natural Science Foundation of Hebei Province","doi-asserted-by":"crossref","award":["A2022205024","A2023205009"],"award-info":[{"award-number":["A2022205024","A2023205009"]}],"id":[{"id":"10.13039\/501100003787","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Interdisciplinary Research Foundation of Hebei Normal University","award":["L2024J01"],"award-info":[{"award-number":["L2024J01"]}]},{"name":"Graduate Innovation Grant Program of Hebei Normal University","award":["YCXZZSS202402"],"award-info":[{"award-number":["YCXZZSS202402"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s11590-024-02155-4","type":"journal-article","created":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T21:01:43Z","timestamp":1728853303000},"page":"1007-1016","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An approximation algorithm for the k-prize-collecting hitting set problem"],"prefix":"10.1007","volume":"19","author":[{"given":"Qin","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Hou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gengsheng","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6872-3315","authenticated-orcid":false,"given":"Wen","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,13]]},"reference":[{"key":"2155_CR1","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. J. Algorithms 2, 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"issue":"4","key":"2155_CR2","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/1041680.1041683","volume":"36","author":"R Bar-Yehuda","year":"2004","unstructured":"Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: A unified framework for approximation algorithms, In memoriam: Shimon Even 1935\u20132004. ACM Comput. Surv. 36(4), 422\u2013463 (2004)","journal-title":"ACM Comput. Surv."},{"key":"2155_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, Symposium on Theoretical Aspects of Computer Science, In: Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science, pp. 298\u2013308 (1998)","DOI":"10.1007\/BFb0028569"},{"issue":"2\u20133","key":"2155_CR4","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0004-3702(92)90027-U","volume":"56","author":"J De Kleer","year":"1992","unstructured":"De Kleer, J., Mackworth, A.K., Reiter, R.: Characterizing diagnoses and systems. Artif. Intell. 56(2\u20133), 197\u2013222 (1992)","journal-title":"Artif. Intell."},{"issue":"1","key":"2155_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1137\/15M1055024","volume":"31","author":"A Gainer-Dewar","year":"2017","unstructured":"Gainer-Dewar, A., Vera-Licona, P.: The minimal hitting set generation problem: algorithms and computation. SIAM J. Discrete Math. 31(1), 63\u2013100 (2017)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"2155_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"},{"issue":"5","key":"2155_CR7","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608\u20131623 (2002)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2155_CR8","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation algorithms for set covering and vertex cover problems. SIAM J. Comput. 11(3), 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2155_CR9","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(86)90016-8","volume":"15","author":"NG Hall","year":"1986","unstructured":"Hall, N.G., Hochbaum, D.S.: A fast approximation for the multicovering problem. Discrete Appl. Math. 15(1), 35\u201340 (1986)","journal-title":"Discrete Appl. Math."},{"key":"2155_CR10","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2020.07.014","volume":"844","author":"X Hou","year":"2020","unstructured":"Hou, X., Liu, W., Hou, B.: An approximation algorithm for the $$k$$-prize-collecting multicut on a tree problem. Theor. Comput. Sci. 844, 26\u201333 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"2155_CR11","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s11590-017-1135-8","volume":"13","author":"L Han","year":"2019","unstructured":"Han, L., Xu, D., Du, D., Wu, C.: A $$5$$-approximation algorithm for the $$k$$-prize-collecting Steiner tree problem. Optim. Lett. 13, 573\u2013585 (2019)","journal-title":"Optim. Lett."},{"key":"2155_CR12","doi-asserted-by":"crossref","unstructured":"Karmarkar, N. A.: new polynomial-time algorithm for linear programming, In: Proc. 16th annual ACM symposium on theory of computing (STOC), pp. 302\u2013311 (1984)","DOI":"10.1145\/800057.808695"},{"key":"2155_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. The IBM Research Symposia Series, Plenum Press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"2155_CR14","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1006\/jagm.1997.0872","volume":"25","author":"M Krivelevich","year":"1997","unstructured":"Krivelevich, M.: Approximate set covering in uniform hypergraphs. J. Algorithms 25(1), 118\u2013143 (1997)","journal-title":"J. Algorithms"},{"issue":"3","key":"2155_CR15","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":"8","key":"2155_CR16","doi-asserted-by":"publisher","first-page":"2373","DOI":"10.1007\/s11590-021-01831-z","volume":"16","author":"X Liu","year":"2022","unstructured":"Liu, X., Li, W., Xie, R.: A primal-dual approximation algorithm for the $$k$$-prize-collecting minimum power cover problem. Optim. Lett. 16(8), 2373\u20132385 (2022)","journal-title":"Optim. Lett."},{"issue":"3","key":"2155_CR17","first-page":"17304","volume":"16","author":"X Liu","year":"2023","unstructured":"Liu, X., Li, W., Yang, J.: A primal-dual approximation algorithm for the $$k$$-prize-collecting minimum vertex cover problem with submodular penalties. Front. Comput. Sci. 16(3), 17304 (2023)","journal-title":"Front. Comput. Sci."},{"key":"2155_CR18","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Geometric Discrepancy: An Illustrated Guide (Algorithms and Combinatorics #18), Springer-Verlag, Berlin. (1999)","DOI":"10.1007\/978-3-642-03942-3"},{"issue":"2","key":"2155_CR19","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s11590-018-1367-2","volume":"13","author":"Y Matsuda","year":"2019","unstructured":"Matsuda, Y., Takahashi, S.: A $$4$$-approximation algorithm for $$k$$-prize collecting Steiner tree problems. Optim. Lett. 13(2), 341\u2013348 (2019)","journal-title":"Optim. Lett."},{"issue":"2","key":"2155_CR20","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s00454-004-1116-4","volume":"32","author":"J Matou\u0161ek","year":"2004","unstructured":"Matou\u0161ek, J., Wagner, U.: New constructions of weak $$\\epsilon$$-nets. Discrete Comput. Geom. 32(2), 195\u2013206 (2004)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"2155_CR21","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.disopt.2004.11.002","volume":"2","author":"M Okun","year":"2005","unstructured":"Okun, M.: On approximation of the vertex cover problem in hypergraphs. Discrete Optim. 2(1), 101\u2013111 (2005)","journal-title":"Discrete Optim."},{"issue":"1","key":"2155_CR22","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0004-3702(87)90062-2","volume":"32","author":"R Reiter","year":"1987","unstructured":"Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32(1), 57\u201395 (1987)","journal-title":"Artif. Intell."},{"key":"2155_CR23","doi-asserted-by":"crossref","unstructured":"Saket, R., Sviridenko, M.: New and improved bounds for the minimum set cover problem, In: Proc. 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, In: Lecture Notes in Computer Science, 7408, 288\u2013300 (2012)","DOI":"10.1007\/978-3-642-32512-0_25"},{"key":"2155_CR24","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.dam.2017.08.024","volume":"275","author":"Y Takazawa","year":"2020","unstructured":"Takazawa, Y., Mizuno, S., Kitahara, T.: An approximation algorithm for the partial covering $$0$$-$$1$$ integer program. Discrete Appl. Math. 275, 126\u2013133 (2020)","journal-title":"Discrete Appl. Math."},{"key":"2155_CR25","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer-Verlag, New York (2001)"},{"key":"2155_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11704-020-0368-3","volume":"16","author":"P Zhang","year":"2022","unstructured":"Zhang, P.: The LP-rounding plus greed approach for partial optimization revisited. Front. Comput. Sci. 16, 1\u20139 (2022)","journal-title":"Front. Comput. Sci."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-024-02155-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-024-02155-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-024-02155-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T07:36:49Z","timestamp":1746776209000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-024-02155-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,13]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["2155"],"URL":"https:\/\/doi.org\/10.1007\/s11590-024-02155-4","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2024,10,13]]},"assertion":[{"value":"15 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there is no Conflict of interest regarding the publication of this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}