{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T21:19:31Z","timestamp":1777497571088,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:00:00Z","timestamp":1586217600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:00:00Z","timestamp":1586217600000},"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":["11771013"],"award-info":[{"award-number":["11771013"]}],"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":["11531011"],"award-info":[{"award-number":["11531011"]}],"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":["61751303"],"award-info":[{"award-number":["61751303"]}],"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":["11901533"],"award-info":[{"award-number":["11901533"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Zhejiang Provincial Natural Science Foundation of China","award":["LD19A010001"],"award-info":[{"award-number":["LD19A010001"]}]},{"name":"Zhejiang Provincial Natural Science Foundation of China","award":["LY19A010018"],"award-info":[{"award-number":["LY19A010018"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s10878-020-00567-3","type":"journal-article","created":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T21:23:09Z","timestamp":1586294589000},"page":"1913-1923","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["A primal-dual algorithm for the minimum power partial cover problem"],"prefix":"10.1007","volume":"44","author":[{"given":"Menghong","family":"Li","sequence":"first","affiliation":[]},{"given":"Yingli","family":"Ran","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4191-7598","authenticated-orcid":false,"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,7]]},"reference":[{"key":"567_CR1","doi-asserted-by":"crossref","unstructured":"Bansal N, Pruhs K (2012) Weighted geometric set multi-cover via quasi-uniform sampling. In: ESA, pp 145\u2013156","DOI":"10.1007\/978-3-642-33090-2_14"},{"issue":"2","key":"567_CR2","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 (2001) Using homogeneous weights for approximating the partial cover problem. J Algorithms 39(2):137\u2013144","journal-title":"J Algorithms"},{"issue":"3","key":"567_CR3","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 (2013) A note on multicovering with disk. Comput Geom 46(3):394\u2013399","journal-title":"Comput Geom"},{"issue":"1","key":"567_CR4","first-page":"220","volume":"6","author":"S Bhowmick","year":"2015","unstructured":"Bhowmick S, Varadarajan K, Xue S-K (2015) A constant-factor approximation for multi-covering with disks. Comput Geom 6(1):220\u201324","journal-title":"Comput Geom"},{"key":"567_CR5","unstructured":"Bhowmick S, Inamdar T, Varadarajan K (2017) On metric multi-covering problems. Comput Geom arxiv:1602.04152"},{"key":"567_CR6","doi-asserted-by":"crossref","unstructured":"Chan TM, Granty E, Konemanny J, Sharpe M (2012) Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In: SODA, pp 1576\u20131585","DOI":"10.1137\/1.9781611973099.125"},{"key":"567_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 (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4:233\u2013235","journal-title":"Math Oper Res"},{"key":"567_CR8","doi-asserted-by":"crossref","unstructured":"Freund A, Rawitz D (2003) Combinatorial interpretations of dual fitting and primal fitting. A conference version in WAOA 137\u2013150 A full version in http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.585.9484","DOI":"10.1007\/978-3-540-24592-6_11"},{"issue":"1","key":"567_CR9","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 (2004) Approximation algorithms for partial covering problems. J Algorithms 53(1):55\u201384","journal-title":"J Algorithms"},{"key":"567_CR10","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11:555\u2013556","journal-title":"SIAM J Comput"},{"key":"567_CR11","first-page":"1","volume":"47","author":"T Inamdar","year":"2018","unstructured":"Inamdar T, Varadarajan K (2018) On partial covering for geometric set system. Comput Geom 47:1\u201314","journal-title":"Comput Geom"},{"key":"567_CR12","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9:256\u2013278","journal-title":"J Comput Syst Sci"},{"key":"567_CR13","doi-asserted-by":"crossref","unstructured":"Li MH, Ran YL, Zhang Z (2019) Approximation algorithms for the minimum power partial cover problem. To appear in AAIM\u201919","DOI":"10.1007\/s10878-020-00567-3"},{"issue":"2","key":"567_CR14","doi-asserted-by":"publisher","first-page":"1850026","DOI":"10.1142\/S179383091850026X","volume":"10","author":"P Liu","year":"2018","unstructured":"Liu P, Huang X (2018) Approximation algorithm for partial set multicover versus full set multicover. Discrete Math Algorithms Appl 10(2):1850026","journal-title":"Discrete Math Algorithms Appl"},{"key":"567_CR15","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"NH Mustafa","year":"2010","unstructured":"Mustafa NH, Ray S (2010) Improved results on geometric hitting set problems. Discrete Comput Geom 44:883\u2013895","journal-title":"Discrete Comput Geom"},{"issue":"6","key":"567_CR16","doi-asserted-by":"publisher","first-page":"1650","DOI":"10.1137\/14099317X","volume":"44","author":"NH Mustafa","year":"2015","unstructured":"Mustafa NH, Raman R, Ray S (2015) Quasi-polynomial time approximation scheme for weighted geometric set cover on pseudodisks. SIAM J Comput 44(6):1650\u20131669","journal-title":"SIAM J Comput"},{"key":"567_CR17","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 (2017a) Approximation algorithm for partial positive influence problem in social network. J Combin Optim 33:791\u2013802","journal-title":"J Combin Optim"},{"issue":"1","key":"567_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10878-016-0066-0","volume":"34","author":"Y Ran","year":"2017","unstructured":"Ran Y, Shi Y, Zhang Z (2017b) Local ratio method on partial set multi-cover. J Combin Optim 34(1):1\u201312","journal-title":"J Combin Optim"},{"key":"567_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-019-00513-y","author":"Y Ran","year":"2019","unstructured":"Ran Y, Shi Y, Tang C, Zhang Z (2019) A primal-dual algorithm for the minimum partial set multi-cover problem. J Combin Optim. https:\/\/doi.org\/10.1007\/s10878-019-00513-y","journal-title":"J Combin Optim"},{"key":"567_CR20","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00454-018-9983-2","volume":"60","author":"AB Roy","year":"2018","unstructured":"Roy AB, Govindarajan S, Raman R, Ray S (2018) Packing and covering with non-piercing regions. Discrete Comput Geom 60:471\u2013492","journal-title":"Discrete Comput Geom"},{"issue":"5","key":"567_CR21","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 (1997) Improved performance of the greedy algorithm for partial cover. Inf Process Lett 64(5):251\u2013254","journal-title":"Inf Process Lett"},{"key":"567_CR22","doi-asserted-by":"crossref","unstructured":"Varadarajan K (2010) Weighted geometric set cover via quasi-uniform sampling. In: STOC\u201910, pp 641\u2013648","DOI":"10.1145\/1806689.1806777"},{"key":"567_CR23","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV (2001) Approximation algorithms. Springer, Berlin"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00567-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00567-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00567-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:46:48Z","timestamp":1664354808000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00567-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,7]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["567"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00567-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,7]]},"assertion":[{"value":"7 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}