{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T21:19:11Z","timestamp":1777497551104,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"the national natural science foundation of china","doi-asserted-by":"crossref","award":["12071417"],"award-info":[{"award-number":["12071417"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s11590-021-01831-z","type":"journal-article","created":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T12:02:42Z","timestamp":1637409762000},"page":"2373-2385","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem"],"prefix":"10.1007","volume":"16","author":[{"given":"Xiaofei","family":"Liu","sequence":"first","affiliation":[]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[]},{"given":"Runtao","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,20]]},"reference":[{"key":"1831_CR1","doi-asserted-by":"crossref","unstructured":"Alt, H., Arkin, E.M., Br\u00f6nnimann, H., Erickson, J., Fekete, S.P., Knauer, C., Lenchner, J., Mitchell, J.S.B., Whittlesey, K.: Minimum-cost coverage of point sets by disks. In: Proceedings of 22nd ACM Symposium on Computational Geometry, pp. 449\u2013458. ACM (2006)","DOI":"10.1145\/1137856.1137922"},{"issue":"3","key":"1831_CR2","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.comgeo.2012.10.006","volume":"46","author":"R Bar-Yehuda","year":"2013","unstructured":"Bar-Yehuda, R., Rawitz, D.: A note on multicovering with disk. Comput. Geom. 46(3), 394\u2013399 (2013)","journal-title":"Comput. Geom."},{"key":"1831_CR3","unstructured":"Bhowmick, S., Inamdar, T., Varadarajan, K.: On metric multi-covering problems. arXiv:org\/abs\/1602.04152 (2017)"},{"issue":"1","key":"1831_CR4","first-page":"220","volume":"6","author":"S Bhowmick","year":"2015","unstructured":"Bhowmick, S., Varadarajan, K., Xue, S.: A constant-factor approximation for multi-covering with disks. J. Comput. Geom. 6(1), 220\u2013234 (2015)","journal-title":"J. Comput. Geom."},{"key":"1831_CR5","doi-asserted-by":"crossref","unstructured":"Bil\u00f3, V., Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Geometric clustering to minimize the sum of cluster sizes. In: Proceedings of 13th annual European symposium on algorithm, pp. 460\u2013471. Springer (2005)","DOI":"10.1007\/11561071_42"},{"issue":"2","key":"1831_CR6","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.jcss.2003.07.014","volume":"68","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Panigrahy, R.: Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. 68(2), 417\u2013441 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"1831_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"1831_CR8","doi-asserted-by":"crossref","unstructured":"Freund, A., Rawitz, D.: Combinatorial interpretations of dual fitting and primal fitting. In: Proceedings of approximation and online algorithms, pp. 137\u2013150. Springer (2003)","DOI":"10.1007\/978-3-540-24592-6_11"},{"key":"1831_CR9","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1007\/s11590-020-01632-w","volume":"15","author":"L Guan","year":"2021","unstructured":"Guan, L., Li, W., Xiao, M.: Online algorithms for the mixed ring loading problem with two nodes. Optim. Lett. 15, 1229\u20131239 (2021)","journal-title":"Optim. Lett."},{"key":"1831_CR10","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s11590-017-1135-8","volume":"13","author":"L Han","year":"2017","unstructured":"Han, L., Xu, D., Du, D., Wu, C.: A 5-approximation algorithm for the $$k$$-prize-collecting Steiner tree problem. Optim. Lett. 13, 573\u2013585 (2017)","journal-title":"Optim. Lett."},{"key":"1831_CR11","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2020.07.014","volume":"844","author":"X Hou","year":"2020","unstructured":"Hou, X., Liu, W., Hou, B.: An approximation algorithm for the $$k$$-prize-collecting multicut on a tree problem. Theor. Comput. Sci. 844, 26\u201333 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"1831_CR12","doi-asserted-by":"crossref","unstructured":"Huang, Z., Feng, Q., Wang, J., Xu, J.: PTAS for minimum cost multi-covering with disks. In: Proceedings of the 2021 ACM-SIAM symposium on discrete algorithms, pp. 840\u2013859. SIAM (2021)","DOI":"10.1137\/1.9781611976465.53"},{"issue":"3","key":"1831_CR13","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"1831_CR14","first-page":"1","volume":"39","author":"M Li","year":"2020","unstructured":"Li, M., Ran, Y., Zhang, Z.: A primal-dual algorithm for the minimum power partial cover problem. J. Comb. Optim. 39(3), 1\u201322 (2020)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"1831_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2512448","volume":"13","author":"M Li","year":"2013","unstructured":"Li, M., Yang, Z., Liu, Y.: Sea depth measurement with restricted floating sensors. ACM Trans. Embed. Comput. Syst. 13(1), 1\u201321 (2013)","journal-title":"ACM Trans. Embed. Comput. Syst."},{"issue":"2","key":"1831_CR16","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s11590-018-1367-2","volume":"13","author":"Y Matsuda","year":"2019","unstructured":"Matsuda, Y., Takahashi, S.: A 4-approximation algorithm for $$k$$-prize collecting Steiner tree problems. Optim. Lett. 13(2), 341\u2013348 (2019)","journal-title":"Optim. Lett."},{"key":"1831_CR17","doi-asserted-by":"crossref","unstructured":"Pedrosa, L.L.C., Rosado, H.H.K.: A 2-approximation for the $$k$$-prize-collecting Steiner tree problem. arXiv:1911.09221 (2019)","DOI":"10.1007\/978-3-030-61792-9_7"},{"key":"1831_CR18","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s10898-021-01033-y","volume":"80","author":"Y Ran","year":"2021","unstructured":"Ran, Y., Huang, X., Zhang, Z., Du, D.: Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks. J. Glob. Optim. 80, 661\u2013677 (2021)","journal-title":"J. Glob. Optim."},{"key":"1831_CR19","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/s10878-016-0066-0","volume":"34","author":"Y Ran","year":"2017","unstructured":"Ran, Y., Shi, Y., Zhang, Z.: Local ratio method on partial set multicover. J. Comb. Optim. 34, 302\u2013313 (2017)","journal-title":"J. Comb. Optim."},{"key":"1831_CR20","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1007\/s10878-019-00513-y","volume":"39","author":"Y Ran","year":"2020","unstructured":"Ran, Y., Shi, Y., Tang, C., Zhang, Z.: A primal-dual algorithm for the minimum partial set multi-cover problem. J. Comb. Optim. 39, 725\u2013746 (2020)","journal-title":"J. Comb. Optim."},{"key":"1831_CR21","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1007\/s10878-016-0005-0","volume":"33","author":"Y Ran","year":"2017","unstructured":"Ran, Y., Zhang, Z., Du, H., Zhu, Y.: Approximation algorithm for partial positive influence problem in social network. J. Comb. Optim. 33, 791\u2013802 (2017)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"1831_CR22","first-page":"774","volume":"33","author":"Y Ran","year":"2021","unstructured":"Ran, Y., Zhang, Z., Tang, S., Du, D.: Breaking the $$r_{max}$$ Barrier: enhanced approximation algorithms for partial set multicover problem. INFORMS J. Comput. 33(2), 774\u2013784 (2021)","journal-title":"INFORMS J. Comput."},{"key":"1831_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.03.004","volume":"803","author":"Y Shi","year":"2020","unstructured":"Shi, Y., Ran, Y., Zhang, Z., Du, D.: A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem. Theor. Comput. Sci. 803, 1\u20139 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"1831_CR24","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1007\/s10898-019-00804-y","volume":"75","author":"Y Shi","year":"2019","unstructured":"Shi, Y., Ran, Y., Zhang, Z., Willson, J., Tong, G., Du, D.: Approximation algorithm for the partial set multi-cover problem. J. Glob. Optim. 75, 1133\u20131146 (2019)","journal-title":"J. Glob. Optim."},{"issue":"5","key":"1831_CR25","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P Slav\u00edk","year":"1997","unstructured":"Slav\u00edk, P.: Improved performance of the greedy algorithm for partial cover. Inf. Process. Lett. 64(5), 251\u2013254 (1997)","journal-title":"Inf. Process. Lett."},{"key":"1831_CR26","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"1831_CR27","doi-asserted-by":"crossref","unstructured":"Xing, G., Lu, C., Zhang, Y., Huang, Q., Pless R.: Minimum power configuration in wireless sensor networks. In: Proceedings of the 6th ACM interational symposium on mobile ad hoc networking and computing, pp. 390\u2013401. ACM (2005)","DOI":"10.1145\/1062689.1062738"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01831-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01831-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01831-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T12:54:52Z","timestamp":1665060892000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01831-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,20]]},"references-count":27,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1831"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01831-z","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,20]]},"assertion":[{"value":"16 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2021","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 that they have no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}