{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T14:39:21Z","timestamp":1768747161715,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U20A2068"],"award-info":[{"award-number":["U20A2068"]}],"id":[{"id":"10.13039\/501100001809","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":[[2024,10]]},"DOI":"10.1007\/s10878-024-01215-w","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T17:01:33Z","timestamp":1728320493000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximation algorithm for prize-collecting vertex cover with fairness constraints"],"prefix":"10.1007","volume":"48","author":[{"given":"Mingchao","family":"Zhou","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4191-7598","authenticated-orcid":false,"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"1215_CR1","doi-asserted-by":"crossref","unstructured":"Balas E (2007) The prize collecting traveling salesman problem and its applications. In: The traveling salesman problem and its variations. Springer, pp 663\u2013695","DOI":"10.1007\/0-306-48213-4_14"},{"issue":"6","key":"1215_CR2","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1002\/net.3230190602","volume":"19","author":"E Balas","year":"1989","unstructured":"Balas E (1989) The prize collecting traveling salesman problem. Networks 19(6):621\u2013636","journal-title":"Networks"},{"key":"1215_CR3","doi-asserted-by":"crossref","unstructured":"Bansal N, Khot S (2010) Inapproximability of hypergraph vertex cover and applications to scheduling problems. In: International colloquium on automata, languages, and programming. Springer, pp 250\u2013261","DOI":"10.1007\/978-3-642-14165-2_22"},{"key":"1215_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","journal-title":"Theor Comput Sci"},{"key":"1215_CR5","unstructured":"Bera S, Chakrabarty D, Flores N, Negahbani M (2019) Fair algorithms for clustering. In: NIPS\u201919: proceedings of the 33rd advances in neural information processing systems. Curran Associates Inc, pp 4954\u20134965"},{"key":"1215_CR6","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. Microsoft, Tech. Rep. MSR-TR-2020-32"},{"issue":"12","key":"1215_CR7","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar B, Kardo\u0161 F, Katreni\u010d J, Semani\u0161in G (2011) Minimum k-path vertex cover. Discrete Appl Math 159(12):1189\u20131195","journal-title":"Discrete Appl Math"},{"key":"1215_CR8","unstructured":"Carr RD, Fleischer LK, Leung VJ, Phillips CA (1999) Strengthening integrality gaps for capacitated network design and covering problems. In: SODA\u201900: proceedings of the eleventh annual ACM-SIAM symposium on discrete algorithms"},{"key":"1215_CR9","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s00453-013-9862-4","volume":"72","author":"D Chakrabarty","year":"2015","unstructured":"Chakrabarty D, Chekuri C, Khanna S, Korula N (2015) Approximability of capacitated network design. Algorithmica 72:493\u2013514","journal-title":"Algorithmica"},{"issue":"2","key":"1215_CR10","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":"11","key":"1215_CR11","doi-asserted-by":"publisher","first-page":"1350078","DOI":"10.1142\/S0129183113500782","volume":"24","author":"MO Da Silva","year":"2013","unstructured":"Da Silva MO, Gimenez-Lugo Gustavo A, Da Silva Murilo VG (2013) Vertex cover in complex networks. International Journal of Modern Physics C 24(11):1350078","journal-title":"International Journal of Modern Physics C"},{"key":"1215_CR12","first-page":"319","volume":"231","author":"M Fischetti","year":"1988","unstructured":"Fischetti M, Toth P (1988) An additive approach for the optimal solution of the prize collecting traveling salesman problem. Veh Routing Methods Stud 231:319\u2013343","journal-title":"Veh Routing Methods Stud"},{"issue":"1","key":"1215_CR13","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00053-1","volume":"48","author":"S Guha","year":"2003","unstructured":"Guha S, Hassin R, Khuller S, Or E (2003) Capacitated vertex covering. J Algorithms 48(1):257\u2013270","journal-title":"J Algorithms"},{"key":"1215_CR14","volume":"97","author":"V Gusev Vasily","year":"2020","unstructured":"Gusev Vasily V (2020) The prize collecting traveling salesman problem and its applications. Omega 97:102102","journal-title":"Omega"},{"key":"1215_CR15","volume-title":"A philosophy for a fair society","author":"M Hudson","year":"2023","unstructured":"Hudson M, Miller GJ, Feder K (2023) A philosophy for a fair society. Shepard-Walwyn, London"},{"key":"1215_CR16","doi-asserted-by":"crossref","unstructured":"Javad-Kalbasi M, Dabiri K, Valaee S, Sheikholeslami A (2019) Digitally annealed solution for the vertex cover problem with application in cyber security. In: 2019 IEEE international conference on acoustics, speech and signal processing (ICASSP 2019). IEEE, pp. 2642\u20132646","DOI":"10.1109\/ICASSP.2019.8683696"},{"issue":"1","key":"1215_CR17","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp RM (1975) On the computational complexity of combinatorial problems. Networks 5(1):45\u201368","journal-title":"Networks"},{"key":"1215_CR18","first-page":"219","volume-title":"Reducibility among combinatorial problems","author":"RM Karp","year":"2010","unstructured":"Karp RM (2010) Reducibility among combinatorial problems. Springer, Berlin, pp 219\u2013241"},{"issue":"3","key":"1215_CR19","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1177\/1354856515592507","volume":"23","author":"H Kennedy","year":"2017","unstructured":"Kennedy H, Elgesem D, Miguel C (2017) On fairness: user perspectives on social media data mining. Convergence 23(3):270\u2013288","journal-title":"Convergence"},{"issue":"3","key":"1215_CR20","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 (2008) Vertex cover might be hard to approximate to within 2- $$\\varepsilon $$. J Comput Syst Sci 74(3):335\u2013349","journal-title":"J Comput Syst Sci"},{"key":"1215_CR21","unstructured":"Li B, Li L, Sun A, Wang C, Wang Y (2021) Approximate group fairness for clustering. In: Proceedings of the 38th international conference on machine learning. PMLR, pp 6381\u20136391"},{"key":"1215_CR22","unstructured":"Liu LT, Dean S, Rolf E, Simchowitz M, Hardt M (2018) Delayed impact of fair machine learning. In: Proceedings of the 35th international conference on machine learning. PMLR, pp 3150\u20133158"},{"issue":"3","key":"1215_CR23","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 Comp Sci 17(3):173404","journal-title":"Front Comp Sci"},{"key":"1215_CR24","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s10654-017-0286-3","volume":"32","author":"M Marmot","year":"2017","unstructured":"Marmot M (2017) Social justice, epidemiology and health inequalities. Eur J Epidemiol 32:537\u2013546","journal-title":"Eur J Epidemiol"},{"key":"1215_CR25","doi-asserted-by":"publisher","first-page":"S4","DOI":"10.1016\/j.puhe.2012.05.014","volume":"126","author":"M Marmot","year":"2012","unstructured":"Marmot M, Bell R (2012) Fair society, healthy lives. Public Health 126:S4\u2013S10","journal-title":"Public Health"},{"issue":"6","key":"1215_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3457607","volume":"54","author":"N Mehrabi","year":"2021","unstructured":"Mehrabi N, Morstatter F, Saxena N, Lerman K, Galstyan A (2021) A survey on bias and fairness in machine learning. ACM Comput Surv 54(6):1\u201335","journal-title":"ACM Comput Surv"},{"key":"1215_CR27","unstructured":"Robert Targan, Probability and computing (2009) Lecture Notes. https:\/\/www.cs.princeton.edu\/courses\/archive\/fall09\/cos521\/Handouts\/probabilityandcomputing.pdf"},{"issue":"5","key":"1215_CR28","first-page":"1281","volume":"83","author":"M Rabin","year":"1993","unstructured":"Rabin M (1993) Incorporating fairness into game theory and economics. Am Econ Rev 83(5):1281\u20131302","journal-title":"Am Econ Rev"},{"key":"1215_CR29","doi-asserted-by":"crossref","unstructured":"Safar M, Taha M, Habib S (2007) Modeling the communication problem in wireless sensor networks as a vertex cover. In: 2007 IEEE\/ACS international conference on computer systems and applications. IEEE, pp 592\u2013598","DOI":"10.1109\/AICCSA.2007.370690"},{"key":"1215_CR30","doi-asserted-by":"crossref","unstructured":"Toume K, Kinjo D, Nakamura M (2014) A gpu algorithm for minimum vertex cover problems. In: International conference of computational methods in sciences and engineering 2014 (ICCMSE 2014), AIP conference proceedings, vol 1618. American Institute of Physics, pp 724\u2013727","DOI":"10.1063\/1.4897834"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01215-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01215-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01215-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T19:10:16Z","timestamp":1729192216000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01215-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1215"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01215-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"22 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2024","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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"20"}}