{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T21:40:04Z","timestamp":1741902004026,"version":"3.38.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T00:00:00Z","timestamp":1737331200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T00:00:00Z","timestamp":1737331200000},"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":["J Comb Optim"],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s10878-024-01253-4","type":"journal-article","created":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T18:48:07Z","timestamp":1737398887000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An improved PTAS for covering targets with mobile sensors"],"prefix":"10.1007","volume":"49","author":[{"given":"Nonthaphat","family":"Wongwattanakij","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nattawut","family":"Phetmak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chaiporn","family":"Jaikaeo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7859-8079","authenticated-orcid":false,"given":"Jittat","family":"Fakcharoenphol","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,20]]},"reference":[{"issue":"7","key":"1253_CR1","doi-asserted-by":"publisher","first-page":"1935","DOI":"10.1016\/j.comnet.2012.02.008","volume":"56","author":"HM Ammari","year":"2012","unstructured":"Ammari HM (2012) On the problem of k-coverage in mission-oriented mobile wireless sensor networks. Comput Netw 56(7):1935\u20131950","journal-title":"Comput Netw"},{"issue":"4","key":"1253_CR2","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/S1389-1286(01)00302-4","volume":"38","author":"IF Akyildiz","year":"2002","unstructured":"Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E (2002) Wireless sensor networks: a survey. Comput Netw 38(4):393\u2013422","journal-title":"Comput Netw"},{"issue":"1","key":"1253_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker BS (1994) Approximation algorithms for np-complete problems on planar graphs. J ACM 41(1):153\u2013180","journal-title":"J ACM"},{"issue":"3","key":"1253_CR4","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/937503.937505","volume":"35","author":"C Blum","year":"2003","unstructured":"Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput Surv 35(3):268\u2013308","journal-title":"ACM Comput Surv"},{"key":"1253_CR5","doi-asserted-by":"crossref","unstructured":"Chen Z, Gao X, Wu F, Chen G (2016) A PTAS to minimize mobile sensor movement for target coverage problem. In: IEEE INFOCOM 2016\u2014The 35th annual IEEE international conference on computer communications, pp 1\u20139","DOI":"10.1109\/INFOCOM.2016.7524334"},{"key":"1253_CR6","doi-asserted-by":"crossref","unstructured":"Ding L, Wu W, Willson J, Wu L, Lu Z, Lee W (2012) Constant-approximation for target coverage problem in wireless sensor networks. In: 2012 Proceedings IEEE INFOCOM, pp 1584\u20131592","DOI":"10.1109\/INFCOM.2012.6195527"},{"key":"1253_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-12450-1_13","volume-title":"Approx Online Algorith","author":"T Erlebach","year":"2010","unstructured":"Erlebach T, Mihal\u00e1k M (2010) A (4 + $$\\epsilon $$)-approximation for the minimum-weight dominating set problem in unit disk graphs. In: Bampis E, Jansen K (eds) Approx Online Algorith. Springer, Berlin, pp 135\u2013146"},{"key":"1253_CR8","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.eswa.2017.09.008","volume":"92","author":"M Elhoseny","year":"2018","unstructured":"Elhoseny M, Tharwat A, Yuan X, Hassanien AE (2018) Optimizing k-coverage of mobile WSNS. Expert Syst Appl 92:142\u2013153","journal-title":"Expert Syst Appl"},{"issue":"6","key":"1253_CR9","doi-asserted-by":"publisher","first-page":"3616","DOI":"10.1109\/TNET.2017.2756925","volume":"25","author":"X Gao","year":"2017","unstructured":"Gao X, Chen Z, Fan W, Chen G (2017) Energy efficient algorithms for $$k$$-sink minimum movement target coverage problem in mobile sensor network. IEEE\/ACM Trans Netw 25(6):3616\u20133627","journal-title":"IEEE\/ACM Trans Netw"},{"issue":"7","key":"1253_CR10","doi-asserted-by":"publisher","first-page":"3469","DOI":"10.1109\/TWC.2019.2914199","volume":"18","author":"J Guo","year":"2019","unstructured":"Guo J, Jafarkhani H (2019) Movement-efficient sensor deployment in wireless sensor networks with limited communication range. IEEE Trans Wirel Commun 18(7):3469\u20133484","journal-title":"IEEE Trans Wirel Commun"},{"key":"1253_CR11","doi-asserted-by":"crossref","unstructured":"He S, Chen J, Li X, Shen X, Sun Y (2012) Cost-effective barrier coverage by mobile sensor networks. In: 2012 Proceedings IEEE INFOCOM, pp 819\u2013827","DOI":"10.1109\/INFCOM.2012.6195829"},{"issue":"2","key":"1253_CR12","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"HB Hunt","year":"1998","unstructured":"Hunt HB, Marathe MV, Radhakrishnan V, Ravi SS, Rosenkrantz DJ, Stearns RE (1998) Nc-approximation schemes for np- and pspace-hard problems for geometric graphs. J Algorithms 26(2):238\u2013274","journal-title":"J Algorithms"},{"issue":"3","key":"1253_CR13","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1587\/transinf.2016EDP7277","volume":"100\u2013D","author":"T Khampeerpat","year":"2017","unstructured":"Khampeerpat T, Jaikaeo C (2017) Mobile sensor relocation for nonuniform and dynamic coverage requirements. IEICE Trans Inf Syst 100\u2013D(3):520\u2013530","journal-title":"IEICE Trans Inf Syst"},{"issue":"2","key":"1253_CR14","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1109\/TPDS.2012.141","volume":"24","author":"B Liu","year":"2013","unstructured":"Liu B, Dousse O, Nain P, Towsley D (2013) Dynamic coverage of mobile sensor networks. IEEE Trans Parallel Distrib Syst 24(2):301\u2013311","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"1253_CR15","doi-asserted-by":"crossref","unstructured":"Liu B, Dousse O, Wang J, Saipulla A (2008) Strong barrier coverage of wireless sensor networks. MobiHoc\u201908, New York. Association for Computing Machinery, pp 411\u2013420","DOI":"10.1145\/1374618.1374673"},{"key":"1253_CR16","doi-asserted-by":"crossref","unstructured":"Liang D, Shen H, Chen L (2021) Maximum target coverage problem in mobile wireless sensor networks. Sensors 21(1)","DOI":"10.3390\/s21010184"},{"issue":"2","key":"1253_CR17","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"MV Marathe","year":"1995","unstructured":"Marathe MV, Breu H, Hunt HB, Ravi SS, Rosenkrantz DJ (1995) Simple heuristics for unit disk graphs. Networks 25(2):59\u201368","journal-title":"Networks"},{"issue":"1","key":"1253_CR18","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1109\/TII.2013.2280095","volume":"10","author":"H Mahboubi","year":"2014","unstructured":"Mahboubi H, Moezzi K, Aghdam AG, Sayrafian-Pour K, Marbukh V (2014) Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors. IEEE Trans Industr Inf 10(1):163\u2013174","journal-title":"IEEE Trans Industr Inf"},{"key":"1253_CR19","doi-asserted-by":"crossref","unstructured":"Nieberg T, Hurink J (2005) A PTAS for the minimum dominating set problem in unit disk graphs. In: WAOA. Springer, pp 296\u2013306","DOI":"10.1007\/11671411_23"},{"key":"1253_CR20","volume-title":"Art gallery theorems and algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke J (1987) Art gallery theorems and algorithms. Oxford University Press Inc, Oxford"},{"key":"#cr-split#-1253_CR21.1","doi-asserted-by":"crossref","unstructured":"van Leeuwen EJ (2005) Approximation algorithms for unit disk graphs. In: Kratsch D","DOI":"10.1007\/11604686_31"},{"key":"#cr-split#-1253_CR21.2","unstructured":"(ed) Graph-theoretic concepts in computer science, 31st International workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers. Lecture notes in computer science, vol 3787. Springer, pp 351-361"},{"key":"1253_CR22","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/11785293_30","volume-title":"Algorithm theory\u2014SWAT 2006","author":"EJ van Leeuwen","year":"2006","unstructured":"van Leeuwen EJ (2006) Better approximation schemes for disk graphs. In: Arge L, Freivalds R (eds) Algorithm theory\u2014SWAT 2006. Springer, Berlin, pp 316\u2013327"},{"key":"1253_CR23","unstructured":"van Leeuwen EJ (2009) Optimization and approximation on systems of geometric objects. PhD thesis, University of Amsterdam"},{"issue":"4","key":"1253_CR24","doi-asserted-by":"publisher","first-page":"32:1","DOI":"10.1145\/1978802.1978811","volume":"43","author":"B Wang","year":"2011","unstructured":"Wang B (2011) Coverage problems in sensor networks: a survey. ACM Comput Surv 43(4):32:1-32:53","journal-title":"ACM Comput Surv"},{"issue":"2","key":"1253_CR25","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1109\/TMC.2007.70708","volume":"7","author":"Y-C Wang","year":"2008","unstructured":"Wang Y-C, Chun-Chi H, Tseng Y-C (2008) Efficient placement and dispatch of sensors in a wireless sensor network. IEEE Trans Mob Comput 7(2):262\u2013274","journal-title":"IEEE Trans Mob Comput"},{"issue":"13","key":"1253_CR26","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1016\/j.comcom.2009.05.004","volume":"32","author":"B Wang","year":"2009","unstructured":"Wang B, Lim HB, Ma D (2009) A survey of movement strategies for improving network coverage in wireless sensor networks. Comput Commun 32(13):1427\u20131436","journal-title":"Comput Commun"},{"issue":"9","key":"1253_CR27","doi-asserted-by":"publisher","first-page":"1280","DOI":"10.1109\/TPDS.2007.70808","volume":"19","author":"Y-C Wang","year":"2008","unstructured":"Wang Y-C, Tseng Y-C (2008) Distributed deployment schemes for mobile wireless sensor networks to ensure multilevel coverage. IEEE Trans Parallel Distrib Syst 19(9):1280\u20131294","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"1253_CR28","doi-asserted-by":"crossref","unstructured":"Wu W, Zhang Z, Lee W, Du D-Z (2020) Optimal coverage in wireless sensor networks. Number 978-3-030-52824-9 in Springer optimization and its applications. Springer","DOI":"10.1007\/978-3-030-52824-9"},{"key":"1253_CR29","doi-asserted-by":"crossref","unstructured":"Xu X, Song M (2014) Restricted coverage in wireless networks. In: IEEE INFOCOM 2014\u2014IEEE conference on computer communications, pp 558\u2013564","DOI":"10.1109\/INFOCOM.2014.6847980"},{"issue":"12","key":"1253_CR30","doi-asserted-by":"publisher","first-page":"2292","DOI":"10.1016\/j.comnet.2008.04.002","volume":"52","author":"J Yick","year":"2008","unstructured":"Yick J, Mukherjee B, Ghosal D (2008) Wireless sensor network survey. Comput Netw 52(12):2292\u20132330","journal-title":"Comput Netw"},{"issue":"1","key":"1253_CR31","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/972627.972631","volume":"3","author":"Y Zou","year":"2004","unstructured":"Zou Y, Chakrabarty K (2004) Sensor deployment and target localization in distributed sensor networks. ACM Trans Embed Comput Syst 3(1):61\u201391","journal-title":"ACM Trans Embed Comput Syst"},{"issue":"3","key":"1253_CR32","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10898-008-9384-9","volume":"45","author":"Z Zhang","year":"2009","unstructured":"Zhang Z, Gao X, Weili W, Ding-Zhu D (2009) A ptas for minimum connected dominating set in 3-dimensional wireless sensor networks. J Global Optim 45(3):451\u2013458","journal-title":"J Global Optim"},{"issue":"3","key":"1253_CR33","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.tcs.2009.06.022","volume":"412","author":"F Zou","year":"2011","unstructured":"Zou F, Wang Y, Xiao-Hua X, Li X, Hongwei D, Wan P, Weili W (2011) New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theor Comput Sci 412(3):198\u2013208","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01253-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01253-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01253-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T21:06:57Z","timestamp":1741900017000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01253-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,20]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["1253"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01253-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,1,20]]},"assertion":[{"value":"17 December 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare they have no financial interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"20"}}