{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,12]],"date-time":"2026-10-12T16:55:16Z","timestamp":1791824116838,"version":"4.3.4"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T00:00:00Z","timestamp":1790121600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T00:00:00Z","timestamp":1790121600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100005064","name":"Hebei Province Science and Technology Support Program","doi-asserted-by":"publisher","award":["246Z7605G"],"award-info":[{"award-number":["246Z7605G"]}],"id":[{"id":"10.13039\/501100005064","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":[[2026,10]]},"DOI":"10.1007\/s10878-026-01476-7","type":"journal-article","created":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T05:32:04Z","timestamp":1790141524000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An FPT approximation algorithm for the partition set cover problem with penalties"],"prefix":"10.1007","volume":"52","author":[{"given":"Hao","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bo","family":"Hou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gengsheng","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ke","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6872-3315","authenticated-orcid":false,"given":"Wen","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,9,23]]},"reference":[{"key":"1476_CR1","doi-asserted-by":"publisher","unstructured":"Adamczyk M, Byrka J, Marcinkowski J, Meesum SM, W\u0142odarczyk M (2019) Constant-factor FPT approximation for capacitated $$k$$-median. In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019). pp 1\u201314. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.1","DOI":"10.4230\/LIPIcs.ESA.2019.1"},{"key":"1476_CR2","doi-asserted-by":"publisher","unstructured":"Bandyapadhyay S, Lochet W, Saurabh S (2023) FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii. In: Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023), pp. 1\u201314. https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2023.12","DOI":"10.4230\/LIPIcs.SoCG.2023.12"},{"issue":"2","key":"1476_CR3","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 (2001) Using homogeneous weights for approximating the partial cover problem. J Algorithms 39(2):137\u2013144. https:\/\/doi.org\/10.1006\/jagm.2000.1150","journal-title":"J Algorithms"},{"key":"1476_CR4","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. https:\/\/doi.org\/10.1016\/j.tcs.2014.04.006","journal-title":"Theor Comput Sci"},{"key":"1476_CR5","unstructured":"Bird S, Dud\u00edk M, Edgar R, Horn B, Lutz R, Milan V, Sameki M, Wallach H, Walker K (2020) Fairlearn: A toolkit for assessing and improving fairness in AI.(MSR-TR-2020-32 Technical Report Microsoft Research)"},{"issue":"3","key":"1476_CR6","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1051\/ita\/2016022\/","volume":"50","author":"\u00c9 Bonnet","year":"2016","unstructured":"Bonnet \u00c9, Paschos VT, Sikora F (2016) Parameterized exact and approximation algorithms for maximum $$k$$-set cover and related satisfiability problems. RAIRO Theor Inform Appl 50(3):227\u2013240. https:\/\/doi.org\/10.1051\/ita\/2016022\/","journal-title":"RAIRO Theor Inform Appl"},{"key":"1476_CR7","doi-asserted-by":"publisher","unstructured":"Brankovic L, Fernau H (2012) Parameterized approximation algorithms for hitting set. In: Proceedings of the 9th International Workshop on Approximation and Online Algorithms (WAOA 2011), pp. 63\u201376. https:\/\/doi.org\/10.1007\/978-3-642-29116-6_6","DOI":"10.1007\/978-3-642-29116-6_6"},{"issue":"4","key":"1476_CR8","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1137\/18M1166869","volume":"49","author":"P Chalermsook","year":"2020","unstructured":"Chalermsook P, Cygan M, Kortsarz G, Laekhanukit B, Manurangsi P, Nanongkai D, Trevisan L (2020) From Gap-ETH to FPT-inapproximability: Clique, dominating set, and more. SIAM J Comput 49(4):772\u2013810. https:\/\/doi.org\/10.1137\/18M1166869","journal-title":"SIAM J Comput"},{"key":"1476_CR9","doi-asserted-by":"publisher","unstructured":"Chen X, Xu D, Xu Y, Zhang Y (2024) Parameterized approximation algorithms for sum-of-radii clustering and variants. In: Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024), pp. 20666\u201320673. https:\/\/doi.org\/10.1609\/aaai.v38i18.30053","DOI":"10.1609\/aaai.v38i18.30053"},{"issue":"3","key":"1476_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal V (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4(3):233\u2013235. https:\/\/doi.org\/10.1287\/moor.4.3.233","journal-title":"Math Oper Res"},{"key":"1476_CR11","doi-asserted-by":"publisher","unstructured":"Devanur NR, Mihail M, Vazirani VV (2003) Strategyproof cost-sharing mechanisms for set cover and facility location games. In: Proceedings of the 4th ACM Conference on Electronic Commerce (EC 2003), pp. 108\u2013114. https:\/\/doi.org\/10.1145\/779928.779942","DOI":"10.1145\/779928.779942"},{"key":"1476_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey RG, Fellows MR (2013) Fundamentals of parameterized complexity. Springer, London"},{"issue":"4","key":"1476_CR13","doi-asserted-by":"publisher","first-page":"634","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):634\u2013652. https:\/\/doi.org\/10.1145\/285055.285059","journal-title":"J ACM"},{"issue":"6","key":"1476_CR14","doi-asserted-by":"publisher","first-page":"146","DOI":"10.3390\/a13060146","volume":"13","author":"AE Feldmann","year":"2020","unstructured":"Feldmann AE, Karthik CS, Lee E, Manurangsi P (2020) A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms 13(6):146. https:\/\/doi.org\/10.3390\/a13060146","journal-title":"Algorithms"},{"key":"1476_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4886-6","volume-title":"Fairness","author":"N Francez","year":"1986","unstructured":"Francez N (1986) Fairness. Springer, New York"},{"issue":"1","key":"1476_CR16","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. https:\/\/doi.org\/10.1016\/j.jalgor.2004.04.002","journal-title":"J Algorithms"},{"key":"1476_CR17","doi-asserted-by":"publisher","unstructured":"Goyal D, Jaiswal R, Kumar A (2020) FPT approximation for constrained metric $$k$$-median\/means. In: Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). pp 1\u201317. https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2020.14","DOI":"10.4230\/LIPIcs.IPEC.2020.14"},{"key":"1476_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Springer, Berlin, Heidelberg"},{"issue":"3","key":"1476_CR19","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. https:\/\/doi.org\/10.1137\/0211045","journal-title":"SIAM J Comput"},{"key":"1476_CR20","unstructured":"Inamdar T (2020) Covering and clustering with outliers and other constraints. Doctoral dissertation. University of Iowa"},{"key":"1476_CR21","doi-asserted-by":"publisher","unstructured":"Jacobs AZ, Wallach H (2021) Measurement and fairness. In: Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency (FAccT 2021), pp. 375\u2013385. https:\/\/doi.org\/10.1145\/3442188.3445901","DOI":"10.1145\/3442188.3445901"},{"issue":"3","key":"1476_CR22","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 Syst Sci 9(3):256\u2013278. https:\/\/doi.org\/10.1016\/S0022-0000(74)80044-9","journal-title":"J Comput Syst Sci"},{"key":"1476_CR23","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-540-68279-0_8","volume-title":"50 Years of Integer Programming 1958\u20132008","author":"RM Karp","year":"2010","unstructured":"Karp RM (2010) Reducibility among combinatorial problems. In: J\u00fcnger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA (eds) 50 Years of Integer Programming 1958\u20132008. Springer, Berlin, Heidelberg, pp 219\u2013241"},{"key":"1476_CR24","volume-title":"The computational complexity of machine learning","author":"MJ Kearns","year":"1990","unstructured":"Kearns MJ (1990) The computational complexity of machine learning. MIT Press, Cambridge, MA"},{"issue":"4","key":"1476_CR25","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(4):489\u2013509. https:\/\/doi.org\/10.1007\/s00453-009-9317-0","journal-title":"Algorithmica"},{"issue":"5","key":"1476_CR26","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1145\/3610302","volume":"14","author":"Y Li","year":"2023","unstructured":"Li Y, Chen H, Xu S, Ge Y, Tan J, Liu S, Zhang Y (2023) Fairness in recommendation: Foundations, methods, and applications. ACM Trans Intell Syst Technol 14(5):95. https:\/\/doi.org\/10.1145\/3610302","journal-title":"ACM Trans Intell Syst Technol"},{"key":"1476_CR27","doi-asserted-by":"publisher","unstructured":"Lin B, Ren X, Sun Y, Wang X (2023) Constant approximating parameterized $$k$$-SETCOVER is $$W[2]$$-hard. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). pp 3305\u20133316. https:\/\/doi.org\/10.1137\/1.9781611977554.ch126","DOI":"10.1137\/1.9781611977554.ch126"},{"key":"1476_CR28","doi-asserted-by":"publisher","unstructured":"Liu X, Li W (2025) Approximation algorithm for prize-collecting hypergraph vertex cover with fairness constraints. In: Proceedings of the 31st International Computing and Combinatorics Conference (COCOON 2025), pp. 41\u201352. https:\/\/doi.org\/10.1007\/978-981-95-0218-9_4","DOI":"10.1007\/978-981-95-0218-9_4"},{"issue":"3","key":"1476_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-022-1665-9","volume":"17","author":"X Liu","year":"2023","unstructured":"Liu X, Li W, Yang J (2023) A primal-dual approximation algorithm for the $$k$$-prize-collecting minimum vertex cover problem with submodular penalties. Front Comput Sci 17(3):173404. https:\/\/doi.org\/10.1007\/s11704-022-1665-9","journal-title":"Front Comput Sci"},{"key":"1476_CR30","doi-asserted-by":"publisher","unstructured":"Lokshtanov D, Sahu A, Saurabh S, Surianarayanan V, Xue J (2025) Parameterized approximation for capacitated $$d$$-hitting set with hard capacities. In: Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA 2025). pp 1565\u20131592. https:\/\/doi.org\/10.1137\/1.9781611978322.48","DOI":"10.1137\/1.9781611978322.48"},{"issue":"4","key":"1476_CR31","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(4):383\u2013390. https:\/\/doi.org\/10.1016\/0012-365X(75)90058-8","journal-title":"Discrete Math"},{"issue":"1","key":"1476_CR32","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx D (2008) Parameterized complexity and approximation algorithms. Comput J 51(1):60\u201378. https:\/\/doi.org\/10.1093\/comjnl\/bxm048","journal-title":"Comput J"},{"issue":"20","key":"1476_CR33","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1016\/j.ipl.2009.07.016","volume":"109","author":"D Marx","year":"2009","unstructured":"Marx D, Razgon I (2009) Constant-ratio fixed-parameter approximation of the edge multicut problem. Inf Process Lett 109(20):1161\u20131166. https:\/\/doi.org\/10.1016\/j.ipl.2009.07.016","journal-title":"Inf Process Lett"},{"key":"1476_CR34","doi-asserted-by":"publisher","unstructured":"Marx D, Razgon I (2011) Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011). pp 469\u2013478. https:\/\/doi.org\/10.1145\/1993636.1993699","DOI":"10.1145\/1993636.1993699"},{"issue":"3","key":"1476_CR35","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/3494672","volume":"55","author":"D Pessach","year":"2022","unstructured":"Pessach D, Shmueli E (2022) A review on fairness in machine learning. ACM Comput Surv 55(3):51. https:\/\/doi.org\/10.1145\/3494672","journal-title":"ACM Comput Surv"},{"issue":"5","key":"1476_CR36","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/s10878-025-01317-z","volume":"49","author":"Q Wang","year":"2025","unstructured":"Wang Q, Hou B, Zhang G, Zhou Y, Liu W (2025) Approximation algorithms for the partition set cover problem with penalties. J Comb Optim 49(5):76. https:\/\/doi.org\/10.1007\/s10878-025-01317-z","journal-title":"J Comb Optim"},{"issue":"1\u20132","key":"1476_CR37","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0954-1810(97)00006-X","volume":"12","author":"F Wen","year":"1998","unstructured":"Wen F, Chang C (1998) A new approach to fault diagnosis in electrical distribution networks using a genetic algorithm. Artif Intell Eng 12(1\u20132):69\u201380. https:\/\/doi.org\/10.1016\/S0954-1810(97)00006-X","journal-title":"Artif Intell Eng"},{"key":"1476_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jnca.2016.08.015","volume":"75","author":"H Zannat","year":"2016","unstructured":"Zannat H, Akter T, Tasnim M, Rahman A (2016) The coverage problem in visual sensor networks: A target-oriented approach. J Netw Comput Appl 75:1\u201315. https:\/\/doi.org\/10.1016\/j.jnca.2016.08.015","journal-title":"J Netw Comput Appl"},{"key":"1476_CR39","doi-asserted-by":"publisher","unstructured":"Zhou J, Zhang Z, Guo J (2025) An FPT factor-$$11$$ approximation algorithm for TSP. In: Proceedings of the 31st International Computing and Combinatorics Conference (COCOON 2025), pp. 283\u2013296. https:\/\/doi.org\/10.1007\/978-981-95-0218-9_21","DOI":"10.1007\/978-981-95-0218-9_21"},{"key":"1476_CR40","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.dam.2025.05.010","volume":"373","author":"M Zhou","year":"2025","unstructured":"Zhou M, Zhang Z (2025) Approximation algorithm for prize-collecting weighted set cover with fairness constraints. Discrete Appl Math 373:301\u2013315. https:\/\/doi.org\/10.1016\/j.dam.2025.05.010","journal-title":"Discrete Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01476-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-026-01476-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01476-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,12]],"date-time":"2026-10-12T16:33:22Z","timestamp":1791822802000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-026-01476-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9,23]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,10]]}},"alternative-id":["1476"],"URL":"https:\/\/doi.org\/10.1007\/s10878-026-01476-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,9,23]]},"assertion":[{"value":"2 December 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 September 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that there is no conflict of interest regarding the publication of this paper.","order":1,"name":"Ethics","label":"Conflict of interest","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"26"}}