{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:07:40Z","timestamp":1757621260126,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":24,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819502172"},{"type":"electronic","value":"9789819502189"}],"license":[{"start":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T00:00:00Z","timestamp":1754179200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T00:00:00Z","timestamp":1754179200000},"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":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-0218-9_4","type":"book-chapter","created":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T21:09:11Z","timestamp":1754168951000},"page":"41-52","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithm for\u00a0Prize-Collecting Hypergraph Vertex Cover with\u00a0Fairness Constraints"],"prefix":"10.1007","author":[{"given":"Xiaofei","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,3]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Springer, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"4_CR2","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":"3","key":"4_CR3","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 the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"4_CR4","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(2), 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"key":"4_CR5","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, STACS 98, pp. 298\u2013308. Springer, Berlin (1998)","DOI":"10.1007\/BFb0028569"},{"issue":"2","key":"4_CR6","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. J. Algorithms 39(2), 137\u2013144 (2001)","journal-title":"J. Algorithms"},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0377-2217(02)00071-1","volume":"140","author":"DS Hochbaum","year":"2002","unstructured":"Hochbaum, D.S.: Solving integer programs over monotone inequalities in three variables: a framework for half integrality and good approximations. Eur. J. Oper. Res. 140(2), 291\u2013321 (2002)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"4_CR8","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/050625382","volume":"19","author":"R Bar-Yehuda","year":"2005","unstructured":"Bar-Yehuda, R., Dror, R.: On the equivalence between the primal-dual schema and the local ratio technique. SIAM J. Discret. Math. 19(3), 762\u2013797 (2005)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"4_CR9","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.: A primal-dual approximation algorithm for the $$k$$-prize-collecting minimum vertex cover problem with submodular penalties. Front. Comp. Sci. 17(3), 173404 (2023)","journal-title":"Front. Comp. Sci."},{"issue":"4","key":"4_CR10","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC 2014, pp. 624\u2013633. Association for Computing Machinery, New York (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-14165-2_22","volume-title":"Automata, Languages and Programming","author":"N Bansal","year":"2010","unstructured":"Bansal, N., Khot, S.: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 250\u2013261. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14165-2_22"},{"key":"4_CR13","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.: A unified approach to approximating partial covering problems. Algorithmica 59, 489\u2013509 (2011)","journal-title":"Algorithmica"},{"issue":"1","key":"4_CR14","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":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1017\/S0960129524000124","volume":"34","author":"X Liu","year":"2024","unstructured":"Liu, X., Li, W.: An approximation algorithm for the K-prize-collecting multicut problem in trees with submodular penalties. Math. Struct. Comput. Sci. 34(3), 193\u2013210 (2024)","journal-title":"Math. Struct. Comput. Sci."},{"issue":"1","key":"4_CR16","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1137\/130919416","volume":"29","author":"V Guruswami","year":"2015","unstructured":"Guruswami, V., Sachdeva, S., Saket, R.: Inapproximability of minimum vertex cover on $$k$$-uniform $$k$$-partite hypergraphs. SIAM J. Discret. Math. 29(1), 36\u201358 (2015)","journal-title":"SIAM J. Discret. Math."},{"key":"4_CR17","unstructured":"Lov\u00e1sz, L.: On minimax theorems of combinatorics. Doctoral thesis, Mathematiki Lapok, 26, 209\u2013264 (1975)"},{"key":"4_CR18","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, M.J.: Approximation algorithm for prize-collecting vertex cover with fairness constraints. Algorithmica 84, 1\u201312 (2022)","journal-title":"Algorithmica"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2014.04.006","volume":"555","author":"SK Bera","year":"2014","unstructured":"Bera, S.K., Gupta, S., Kumar, A., Roy, S.: Approximation algorithms for the partition vertex cover problem. Theoret. Comput. Sci. 555, 2\u20138 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR20","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.: On colorful vertex and edge cover problems. Algorithmica 85, 3816\u20133827 (2023)","journal-title":"Algorithmica"},{"key":"4_CR21","unstructured":"Inamdar, T., Varadarajan, K.:. On the partition set cover problem. CoRR. arxiv:1809.06506 (2018)"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s10878-024-01215-w","volume":"48","author":"M Zhou","year":"2024","unstructured":"Zhou, M., Zhang, Z., Ding-Zhu, D.: Approximation algorithm for vertex cover with multiple covering constraints. J. Comb. Optim. 48, 20 (2024)","journal-title":"J. Comb. Optim."},{"key":"4_CR23","doi-asserted-by":"publisher","unstructured":"Wang, Q., Hou, B., Zhang, G., Liu, W.: Approximation algorithms for the partition set cover problem with penalties. SSRN. https:\/\/doi.org\/10.2139\/ssrn.4903712 (2024)","DOI":"10.2139\/ssrn.4903712"},{"key":"4_CR24","unstructured":"Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Programming. Athena-Scientific (1997)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-0218-9_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T12:40:59Z","timestamp":1757335259000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-0218-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,3]]},"ISBN":["9789819502172","9789819502189"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-0218-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,8,3]]},"assertion":[{"value":"3 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors declare that they have no known competing financial interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/cocoon2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}