{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:12:48Z","timestamp":1757617968833,"version":"3.44.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T00:00:00Z","timestamp":1747785600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T00:00:00Z","timestamp":1747785600000},"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":"publisher","award":["A2022205024","A2023205009"],"award-info":[{"award-number":["A2022205024","A2023205009"]}],"id":[{"id":"10.13039\/501100003787","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008238","name":"Hebei Provincial Department of Science and Technology","doi-asserted-by":"publisher","award":["246Z7605G"],"award-info":[{"award-number":["246Z7605G"]}],"id":[{"id":"10.13039\/501100008238","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008970","name":"Hebei Normal University of Science and Technology","doi-asserted-by":"publisher","award":["L2024J01","L2024J01"],"award-info":[{"award-number":["L2024J01","L2024J01"]}],"id":[{"id":"10.13039\/100008970","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s10878-025-01317-z","type":"journal-article","created":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T16:36:01Z","timestamp":1747845361000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for the partition set cover problem with penalties"],"prefix":"10.1007","volume":"49","author":[{"given":"Qi","family":"Wang","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"}]},{"given":"Yisheng","family":"Zhou","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":[[2025,5,21]]},"reference":[{"key":"1317_CR1","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1137\/1018115","volume":"18","author":"E Balas","year":"1976","unstructured":"Balas E, Padberg MW (1976) Set partitioning: a survey. SIAM Review 18:710\u2013760","journal-title":"SIAM Review"},{"issue":"12","key":"1317_CR2","doi-asserted-by":"publisher","first-page":"3816","DOI":"10.1007\/s00453-023-01164-6","volume":"85","author":"S Bandyapadhyay","year":"2023","unstructured":"Bandyapadhyay S, Banik A, Bhore S (2023) On colorful vertex and edge cover problems. Algorithmica 85(12):3816\u20133827","journal-title":"Algorithmica"},{"key":"1317_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2014.04.006","volume":"555","author":"SK Bera","year":"2014","unstructured":"Bera SK, Gupta S, Kumar A, Roy S (2014) Approximation algorithms for the partition vertex cover problem. Theor Comput Sci 555:2\u20138","journal-title":"Theor Comput Sci"},{"key":"1317_CR4","unstructured":"Carr RD, Fleischer L, Leung VJ, Phillips CA (2000) Strengthening integrality gaps for capacitated network design and covering problems. In: David B. Shmoys (Ed.), Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 106\u2013115"},{"issue":"2","key":"1317_CR5","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1007\/s10878-022-00874-x","volume":"44","author":"C Chekuri","year":"2022","unstructured":"Chekuri C, Inamdar T, Quanrud K, Varadarajan K, Zhang Z (2022) Algorithms for covering multiple submodular constraints and applications. J Comb Optim 44(2):979\u20131010","journal-title":"J Comb Optim"},{"issue":"3","key":"1317_CR6","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal V (1979) A greedy heuristic for the set covering problem. Math Oper Res 4(3):233\u2013235","journal-title":"Math Oper Res"},{"issue":"4","key":"1317_CR7","doi-asserted-by":"crossref","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of $$\\ln n$$ for approximating set cover. J ACM 45(4):634652","journal-title":"J ACM"},{"issue":"1","key":"1317_CR8","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 (2004) Approximation algorithms for partial covering problems. J Algorithms 53(1):55\u201384","journal-title":"J Algorithms"},{"key":"1317_CR9","first-page":"207","volume":"11","author":"JS Guo","year":"2023","unstructured":"Guo JS, Liu W, Hou B (2023) An approximation algorithm for $$P$$-prize-collecting set cover problem. J Oper Res Soc China 11:207\u2013217","journal-title":"J Oper Res Soc China"},{"issue":"2","key":"1317_CR10","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1109\/TCBB.2009.54","volume":"8","author":"ZY He","year":"2011","unstructured":"He ZY, Yang C, Yu WC (2011) A partial set covering model for protein mixture identification using mass spectrometry data. IEEE\/ACM Trans Comput Biology Bioinform 8(2):368\u2013380","journal-title":"IEEE\/ACM Trans Comput Biology Bioinform"},{"issue":"3","key":"1317_CR11","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11(3):555\u2013556","journal-title":"SIAM J Comput"},{"issue":"1","key":"1317_CR12","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum DS, Maass W (1985) Approximation schemes for covering and packing problems in image processing and VLSI. J ACM 32(1):130\u2013136","journal-title":"J ACM"},{"key":"1317_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-021-00885-w","volume":"84","author":"E Hung","year":"2022","unstructured":"Hung E, Kao MJ (2022) Approximation algorithm for vertex cover with multiple covering constraints. Algorithmica 84:1\u201312","journal-title":"Algorithmica"},{"key":"1317_CR14","unstructured":"Inamdar T (2020) Covering and Clustering with Outliers and Other Constraints. Thesis (Ph.D.)-The University of Iowa ProQuest LLC, Ann Arbor, MI, pp. 187"},{"key":"1317_CR15","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput System Sci 9:256\u2013278","journal-title":"J Comput System Sci"},{"key":"1317_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of Computer Computations. Plenum Press, New York, The IBM Research Symposia Series, pp 85\u2013103"},{"key":"1317_CR17","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00453-009-9317-0","volume":"59","author":"J K\u00f6nemann","year":"2011","unstructured":"K\u00f6nemann J, Parekh O, Segev D (2011) A unified approach to approximating partial covering problems. Algorithmica 59:489\u2013509","journal-title":"Algorithmica"},{"issue":"3","key":"1317_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-022-1665-9","volume":"17","author":"XF Liu","year":"2023","unstructured":"Liu XF, Li WD, Yang JH (2023) A primal-dual approxiamtion algorithm for the $$k$$-prize-collecting minimum vertex problem with submodular penalties. Front Comput Sci 17(3):173404","journal-title":"Front Comput Sci"},{"key":"1317_CR19","unstructured":"Liu W, Wang Q, Gao SG, Hou B (2024) Approximation algorithms for the partial covering $$0$$-$$1$$ integer program with penalties. Preprint"},{"key":"1317_CR20","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz L (1975) On the ratio of optimal integral and fractional covers. Discrete Math 13:383\u2013390","journal-title":"Discrete Math"},{"issue":"3","key":"1317_CR21","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/S0377-2217(00)00205-8","volume":"133","author":"M Ohlsson","year":"2001","unstructured":"Ohlsson M, Peterson C, S\u00f6derberg B (2001) An efficient mean field approach to the set covering problem. Eur J Oper Res 133(3):583\u2013595","journal-title":"Eur J Oper Res"},{"key":"1317_CR22","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 (2020) An approximation algorithm for the partial covering $$0$$-$$1$$ integer program. Discrete Appl Math 275:126\u2013133","journal-title":"Discrete Appl Math"},{"issue":"2","key":"1317_CR23","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.orl.2022.02.003","volume":"50","author":"Y Takazawa","year":"2022","unstructured":"Takazawa Y (2022) Approximation algorithm for the stochastic prize-collecting set multicover problem. Oper Res Lett 50(2):224\u2013228","journal-title":"Oper Res Lett"},{"issue":"2","key":"1317_CR24","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10255-014-0282-2","volume":"30","author":"J Tu","year":"2014","unstructured":"Tu J, Du J, Yang F (2014) An iterative rounding $$2$$-approximation algorithm for the $$k$$-partial vertex cover problem. Acta Math Appl Sin Engl Ser 30(2):271\u2013278","journal-title":"Acta Math Appl Sin Engl Ser"},{"key":"1317_CR25","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV (2001) Approximation Algorithms. Springer-Verlag, New York"},{"issue":"1","key":"1317_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-020-0368-3","volume":"16","author":"P Zhang","year":"2022","unstructured":"Zhang P (2022) The LP-rounding plus greed approach for partial optimization revisited. Front Comput Sci 16(1):161402","journal-title":"Front Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01317-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01317-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01317-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T15:13:14Z","timestamp":1757171594000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01317-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,21]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["1317"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01317-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,5,21]]},"assertion":[{"value":"30 April 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2025","order":2,"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 interests regarding the publication of this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"76"}}