{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T09:39:19Z","timestamp":1776764359739,"version":"3.51.2"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T00:00:00Z","timestamp":1770163200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T00:00:00Z","timestamp":1770163200000},"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":"crossref","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Beijing Natural Science Foundation"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1007\/s00224-026-10260-3","type":"journal-article","created":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T14:28:36Z","timestamp":1770215316000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimum-Cost Mixed Graph Covers with Targeted Weight Constraints"],"prefix":"10.1007","volume":"70","author":[{"given":"Xujin","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiyuan","family":"Deng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaodong","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Changjun","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,4]]},"reference":[{"key":"10260_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2003","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin, Heidelberg (2003)"},{"key":"10260_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"key":"10260_CR3","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems, pp. 85\u2013103. Springer, Boston, MA (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"10260_CR4","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."},{"key":"10260_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, pp. 298\u2013308. Springer, Berlin, Heidelberg (1998)","DOI":"10.1007\/BFb0028569"},{"key":"10260_CR6","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.S.: The t-vertex cover problem: Extending the half integrality framework with budget constraints. In: Proceedings of the 1st International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 111\u2013122. Springer, Berlin, Heidelberg (1998)","DOI":"10.1007\/BFb0053968"},{"issue":"2","key":"10260_CR7","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":"1","key":"10260_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.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"issue":"1","key":"10260_CR9","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s00453-007-9003-z","volume":"55","author":"J Mestre","year":"2009","unstructured":"Mestre, J.: A primal-dual approximation algorithm for partial vertex cover: making educated guesses. Algorithmica 55(1), 227\u2013239 (2009)","journal-title":"Algorithmica"},{"key":"10260_CR10","doi-asserted-by":"crossref","unstructured":"Carnes, T., Shmoys, D.: Primal-dual schema for capacitated covering problems. In: Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization, pp. 288\u2013302. Springer, Berlin, Heidelberg (2008)","DOI":"10.1007\/978-3-540-68891-4_20"},{"key":"10260_CR11","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-981-96-8312-3_6","volume-title":"Frontiers of Algorithmics","author":"X Chen","year":"2025","unstructured":"Chen, X., Deng, X., Hu, X., Wang, C.: Mixed graph covering with target constraints. In: Chau, V., D\u00fcrr, C., Li, M., Lu, P. (eds.) Frontiers of Algorithmics, pp. 78\u201391. Springer, Singapore (2025)"},{"issue":"4","key":"10260_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0167-6377(99)00045-0","volume":"25","author":"T Fujito","year":"1999","unstructured":"Fujito, T.: On approximation of the submodular set cover problem. Oper. Res. Lett. 25(4), 169\u2013174 (1999)","journal-title":"Oper. Res. Lett."},{"key":"10260_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-021-00885-w","volume":"84","author":"E Hung","year":"2021","unstructured":"Hung, E., Kao, M.: Approximation algorithm for vertex cover with multiple covering constraints. Algorithmica 84, 1\u201312 (2021)","journal-title":"Algorithmica"},{"issue":"1","key":"10260_CR14","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.: Capacitated vertex covering. J. Algorithms 48(1), 257\u2013270 (2003)","journal-title":"J. Algorithms"},{"key":"10260_CR15","doi-asserted-by":"crossref","unstructured":"Mkrtchyan, V., Parekh, O., Segev, D., Subramani, K.: The approximability of partial vertex covers in trees. In: International Conference on Current Trends in Theory and Practice of Informatics, pp. 350\u2013360 (2017). Springer","DOI":"10.1007\/978-3-319-51963-0_27"},{"issue":"3","key":"10260_CR16","doi-asserted-by":"publisher","first-page":"2172","DOI":"10.1137\/15M1054328","volume":"31","author":"B Caskurlu","year":"2017","unstructured":"Caskurlu, B., Mkrtchyan, V., Parekh, O., Subramani, K.: Partial vertex cover and budgeted maximum coverage in bipartite graphs. SIAM J. Discret. Math. 31(3), 2172\u20132184 (2017)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"10260_CR17","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463\u2013468 (1975)","journal-title":"J. ACM"},{"key":"10260_CR18","unstructured":"Carr, R.D., Fleischer, L.K., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 106\u2013115. Society for Industrial and Applied Mathematics, USA (2000)"},{"issue":"2","key":"10260_CR19","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s10107-014-0803-z","volume":"153","author":"T Carnes","year":"2015","unstructured":"Carnes, T., Shmoys, D.B.: Primal-dual schema for capacitated covering problems. Math. Program. 153(2), 289\u2013308 (2015)","journal-title":"Math. Program."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10260-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10260-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10260-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T08:42:44Z","timestamp":1776760964000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10260-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,4]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10260"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10260-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,4]]},"assertion":[{"value":"1 December 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2026","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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"4"}}