{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T22:57:59Z","timestamp":1774393079060,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T00:00:00Z","timestamp":1621382400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T00:00:00Z","timestamp":1621382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11901533"],"award-info":[{"award-number":["11901533"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11771013"],"award-info":[{"award-number":["11771013"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004731","name":"Natural Science Foundation of Zhejiang Province","doi-asserted-by":"publisher","award":["LD19A010001"],"award-info":[{"award-number":["LD19A010001"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000001","name":"Natural Science Foundation","doi-asserted-by":"publisher","award":["1907472"],"award-info":[{"award-number":["1907472"]}],"id":[{"id":"10.13039\/501100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s10898-021-01033-y","type":"journal-article","created":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T07:02:54Z","timestamp":1621407774000},"page":"661-677","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks"],"prefix":"10.1007","volume":"80","author":[{"given":"Yingli","family":"Ran","sequence":"first","affiliation":[]},{"given":"Xiaohui","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,19]]},"reference":[{"issue":"6","key":"1033_CR1","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1142\/S021819591100386X","volume":"21","author":"AK Abu-Affash","year":"2011","unstructured":"Abu-Affash, A.K., Carmi, P., Katz, M.J., Morgenstern, G.: Multi cover of a polygon minimizing the sum of areas. Int. J. Comput. Geom. Appl. 21(6), 685\u2013698 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"1033_CR2","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: 22nd ACM Symposium on Computational Geometry, pp. 449\u2013458 (2006)","DOI":"10.1145\/1137856.1137922"},{"key":"1033_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Pruhs, K.: Weighted geometric set multi-cover via quasi-uniform sampling. In: Proceedings of the European Symposium on Algorithms, pp. 145\u2013156 (2012)","DOI":"10.1007\/978-3-642-33090-2_14"},{"issue":"3","key":"1033_CR4","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 disks. Comput. Geom. 46(3), 394\u2013399 (2013)","journal-title":"Comput. Geom."},{"key":"1033_CR5","doi-asserted-by":"crossref","unstructured":"Bhowmick, S., Varadarajan, K.R., Xue, S.K.: A constant-factor approximation for multi-covering with disks. In: Symposium on Computational Geometry, pp. 243\u2013248 (2013)","DOI":"10.1145\/2462356.2462400"},{"issue":"1","key":"1033_CR6","first-page":"220","volume":"6","author":"S Bhowmick","year":"2015","unstructured":"Bhowmick, S., Varadarajan, K.R., Xue, S.K.: A constant-factor approximation for multi-covering with disks. JoCG 6(1), 220\u2013234 (2015)","journal-title":"JoCG"},{"issue":"2","key":"1033_CR7","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/s00453-020-00762-y","volume":"83","author":"S Bhowmick","year":"2021","unstructured":"Bhowmick, S., Inamdar, T., Kasturi, R.: Varadarajan: fault-tolerant covering problems in metric spaces. Algorithmica 83(2), 413\u2013446 (2021)","journal-title":"Algorithmica"},{"key":"1033_CR8","doi-asserted-by":"crossref","unstructured":"Bil\u00f3, V., Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Geometric clustering to minimize the sum of cluster sizes. In: ESA, pp. 460\u2013471 (2005)","DOI":"10.1007\/11561071_42"},{"issue":"4","key":"1033_CR9","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"1033_CR10","unstructured":"Brualdi, R.A.: Introductory Combinatorics. Prentice Hall (2009)"},{"key":"1033_CR11","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"TM Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46, 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"key":"1033_CR12","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Grant, E., K\u00f6nemann, J., Sharpe, M.: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In: SODA, pp. 1576\u20131585 (2012)","DOI":"10.1137\/1.9781611973099.125"},{"issue":"3","key":"1033_CR13","doi-asserted-by":"publisher","first-page":"1770","DOI":"10.1109\/TWC.2020.3036408","volume":"20","author":"Z Cai","year":"2021","unstructured":"Cai, Z., Chen, Q.: Latency-and-coverage aware data aggregation scheduling for multihop battery-free wireless networks. IEEE Trans. Wirel. Commun. 20(3), 1770\u20131784 (2021)","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"1033_CR14","doi-asserted-by":"crossref","unstructured":"Cardei, M., Thai, M., Li, Y., Wu, W.: Energy-efficient target coverage in wireless sensor networks. In: INFOCOM\u201905, Miami (2005)","DOI":"10.1109\/MOBHOC.2006.278579"},{"issue":"2","key":"1033_CR15","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."},{"key":"1033_CR16","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Clarkson, K.L., Har-Peled, S.: On the set multi-cover problem in geometric settings. In: 25th ACM Symposium on Computational Geometry, pp. 341\u2013350 (2009)","DOI":"10.1145\/1542362.1542421"},{"key":"1033_CR17","unstructured":"Chekuri, C., Quanrud, K., Zhang, Z.: On approximating partial set cover and generalizations. arXiv:1907.04413"},{"issue":"2","key":"1033_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"KL Clarkson","year":"1987","unstructured":"Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2(2), 195\u2013222 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"1033_CR19","doi-asserted-by":"crossref","unstructured":"Freund, A., Rawitz, D.: Combinatorial interpretations of dual fitting and primal fitting. A conference version in WAOA, pp. 137\u2013150 (2003) A full version inhttp:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.585.9484","DOI":"10.1007\/978-3-540-24592-6_11"},{"issue":"1","key":"1033_CR20","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"},{"key":"1033_CR21","doi-asserted-by":"crossref","unstructured":"Gupta, H., Das, S., Gu, Q.: Connected sensor cover: self-organization of sensor networks for efficient query execution. In: MobiHoc\u201903, pp. 189\u2013200 (2003)","DOI":"10.1145\/778415.778438"},{"key":"1033_CR22","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\varepsilon $$-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"1033_CR23","first-page":"1","volume":"47","author":"T Inamdar","year":"2018","unstructured":"Inamdar, T., Varadarajan, K.: On partial covering for geometric set system. Comput. Geom. 47, 1\u201314 (2018)","journal-title":"Comput. Geom."},{"issue":"4","key":"1033_CR24","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1016\/j.comnet.2004.08.012","volume":"47","author":"N Lev-Tov","year":"2005","unstructured":"Lev-Tov, N., Peleg, D.: Polynomial time approximation schemes for base station coverage with minimum total radii. Comput. Netw. 47(4), 489\u2013501 (2005)","journal-title":"Comput. Netw."},{"key":"1033_CR25","doi-asserted-by":"crossref","unstructured":"Li, J., Jin, Y.: A PTAS for the weighted unit disk cover problem. In: ICALP, pp. 898\u2013909 (2015)","DOI":"10.1007\/978-3-662-47672-7_73"},{"key":"1033_CR26","unstructured":"Li, M., Ran, Y., Zhang, Z.: Approximation algorithms for the minimum power partial cover problem. In: AAIM2019, LNCS 11640, pp. 1\u201313"},{"key":"1033_CR27","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.tcs.2021.02.033","volume":"864","author":"W Liang","year":"2021","unstructured":"Liang, W., Li, M., Zhang, Z., Huang, X.: Minimum power partial multi-cover on a line. Theor. Comput. Sci. 864, 118\u2013128 (2021)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1033_CR28","doi-asserted-by":"publisher","first-page":"1850026","DOI":"10.1142\/S179383091850026X","volume":"10","author":"P Liu","year":"2018","unstructured":"Liu, P., Huang, X.: Approximation algorithm for partial set multicover versus full set multicover. Discrete Math. Algorithms Appl. 10(2), 1850026 (2018)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"1033_CR29","doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Almost-polynomial ratio ETH-hardness of approximating densest $$k$$-subgraph. In: STOC, pp. 19\u201323 (2017)","DOI":"10.1145\/3055399.3055412"},{"issue":"6","key":"1033_CR30","doi-asserted-by":"publisher","first-page":"1650","DOI":"10.1137\/14099317X","volume":"44","author":"NH Mustafa","year":"2015","unstructured":"Mustafa, N.H., Raman, R., Ray, S.: Quasi-polynomial time approximation scheme for weighted geometric set cover on pseudodisks. SIAM J. Comput. 44(6), 1650\u20131669 (2015)","journal-title":"SIAM J. Comput."},{"key":"1033_CR31","unstructured":"Rajiv, R., Ray, S.: Improved approximation algorithm for set multicover with non-piercing regions. In: 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00f6r Informatik (2020)"},{"key":"1033_CR32","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. Combin. Optim. 39, 725\u2013746 (2020)","journal-title":"J. Combin. Optim."},{"key":"1033_CR33","doi-asserted-by":"crossref","unstructured":"Shi, T., Cheng, S., Li, J., Gao, H., Cai, Z.: Dominating sets construction in RF-based battery-free sensor networks with full coverage guarantee. ACM Trans. Sens. Netw. 15(4), Article 43 (2019)","DOI":"10.1145\/3352486"},{"key":"1033_CR34","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.R.: Weighted geometric set cover via quasi-uniform sampling. In: Proceedings of ACM Symposium on Theory of Computing, pp. 641\u2013648 (2010)","DOI":"10.1145\/1806689.1806777"},{"key":"1033_CR35","doi-asserted-by":"crossref","unstructured":"Wu, W., Zhang, Z., Lee, W., Du, D.-Z.: Optimal Coverage in Wireless Sensor Networks. Springer (2020)","DOI":"10.1007\/978-3-030-52824-9"},{"issue":"6","key":"1033_CR36","doi-asserted-by":"publisher","first-page":"3620","DOI":"10.1109\/TNET.2016.2531688","volume":"24","author":"Z Zhang","year":"2016","unstructured":"Zhang, Z., Willson, J., Lu, Z., Wu, W., Zhu, X., Du, D.-Z.: Approximating maximum lifetime $$k$$-coverage through minimizing weighted $$k$$-cover in homogeneous wireless sensor networks. IEEE\/ACM Trans. Netw. 24(6), 3620\u20133633 (2016)","journal-title":"IEEE\/ACM Trans. Netw."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01033-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-021-01033-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01033-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,7]],"date-time":"2021-07-07T06:17:55Z","timestamp":1625638675000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-021-01033-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,19]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["1033"],"URL":"https:\/\/doi.org\/10.1007\/s10898-021-01033-y","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,19]]},"assertion":[{"value":"21 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}