{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:59:24Z","timestamp":1740142764966,"version":"3.37.3"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T00:00:00Z","timestamp":1648512000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100004271","name":"Sapienza University of Rome","doi-asserted-by":"publisher","award":["RM11715C44AB9878"],"award-info":[{"award-number":["RM11715C44AB9878"]}],"id":[{"id":"10.13039\/501100004271","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,7,13]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this paper, we consider the problem of flying over an area affected by a natural disaster (e.g. an earthquake) with a fleet of self-piloting unmanned aerial vehicles with cameras or other kinds of sensors on board; the aim is to acquire knowledge of the situation before rescuers start working. We model this situation as a new graph theoretical problem; then, we study its complexity providing an approximation ratio that becomes constant in some special (though practically reasonable) cases; finally, we put in relation the approximability of this new problem and of a well-known one. To the best of our knowledge, no previous work has ever considered all together the constraints we take into account from a theoretical point of view, so this is the first very general graph theoretical model for this problem.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac028","type":"journal-article","created":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T20:10:23Z","timestamp":1646856623000},"page":"1586-1594","source":"Crossref","is-referenced-by-count":0,"title":["Modeling and Approximating the Visit of a Set of Sites With a Fleet of UAVs"],"prefix":"10.1093","volume":"66","author":[{"given":"Tiziana","family":"Calamoneri","sequence":"first","affiliation":[{"name":"Computer Science Department , Sapienza University of Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Tavernelli","sequence":"additional","affiliation":[{"name":"Computer Science Department , Sapienza University of Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,3,29]]},"reference":[{"key":"2023071709111493200_ref1","article-title":"Unmanned aerial vehicle (UAV)-based remote sensing to monitor grapevine leaf stripe disease within a vineyard affected by esca complex","volume":"55","author":"Gennaro","year":"2016","journal-title":"Phytopathol. Mediterr."},{"key":"2023071709111493200_ref2","doi-asserted-by":"crossref","first-page":"1111","DOI":"10.1007\/s10878-018-0341-3","article-title":"Approximation algorithms for distance constraint sweep coverage with base stations","volume":"37","author":"Liang","year":"2019","journal-title":"J. Comb. Optim."},{"volume-title":"Proc. Int. l Conf. on Intelligent Unmanned Systems","year":"2014","author":"Sharifi","key":"2023071709111493200_ref3"},{"key":"2023071709111493200_ref4","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.amj.2014.10.011","article-title":"Use of unmanned aerial vehicles for medical product transport","volume":"34","author":"Thiels","year":"2015","journal-title":"Air Med. J."},{"volume-title":"Handbook of Unmanned Aerial Vehicles","year":"2014","author":"Valavanis","key":"2023071709111493200_ref5"},{"key":"2023071709111493200_ref6","first-page":"1","volume-title":"2016 Int. Conf. on Computing, Networking and Communications (ICNC)","author":"Erdelj","year":"2016"},{"key":"2023071709111493200_ref7","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/MPRV.2017.11","article-title":"Help from the sky: Leveraging UAVs for disaster management","volume":"16","author":"Erdelj","year":"2017","journal-title":"IEEE Pervasive Comput."},{"key":"2023071709111493200_ref8","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/j.procs.2019.01.151","article-title":"The uses of unmanned aerial vehicles UAVs- (or drones) in social logistic: Natural disasters response and humanitarian relief aid","volume":"149","author":"Estrada","year":"2019","journal-title":"Procedia Comput. Sci."},{"key":"2023071709111493200_ref9","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-981-13-0992-2_7","volume-title":"Geological Disaster Monitoring Based on Sensor Networks","author":"Luo","year":"2019"},{"key":"2023071709111493200_ref10","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1109\/LWC.2017.2776922","article-title":"Energy-efficient data collection in UAV enabled wireless sensor network","volume":"7","author":"Zhan","year":"2018","journal-title":"IEEE Wirel. Commun."},{"key":"2023071709111493200_ref11","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.dam.2011.09.014","article-title":"Approximation results for a min-max location-routing problem","volume":"160","author":"Xu","year":"2012","journal-title":"Discret. Appl. Math."},{"key":"2023071709111493200_ref12","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","article-title":"The euclidean travelling salesman problem is NP-complete","volume":"4","author":"Papadimitriou","year":"1977","journal-title":"Theor. Comput. Sci."},{"key":"2023071709111493200_ref13","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","article-title":"The multiple traveling salesman problem: An overview of formulations and solution procedures","volume":"34","author":"Bektas","year":"2006","journal-title":"Omega"},{"volume-title":"The Vehicle Routing Problem","year":"2001","author":"Toth","key":"2023071709111493200_ref14"},{"key":"2023071709111493200_ref15","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s10288-020-00433-2","article-title":"Vehicle routing problems over time: A survey","volume":"18","author":"Mor","year":"2020","journal-title":"4OR"},{"key":"2023071709111493200_ref16","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/s10288-016-0306-2","article-title":"Vehicle routing problems with multiple trips","volume":"14","author":"Cattaruzza","year":"2016","journal-title":"4OR"},{"key":"2023071709111493200_ref17","doi-asserted-by":"crossref","first-page":"3223","DOI":"10.1016\/j.dam.2008.05.009","article-title":"A new formulation for the traveling deliveryman problem","volume":"156","author":"M\u00e9ndez-D\u00edaz","year":"2008","journal-title":"Discret. Appl. Math."},{"key":"2023071709111493200_ref18","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.ejor.2013.09.014","article-title":"Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints","volume":"234","author":"Luo","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"2023071709111493200_ref19","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s10732-006-9004-0","article-title":"Metaheuristics for the team orienteering problem","volume":"13","author":"Archetti","year":"2007","journal-title":"J. Heuristics"},{"key":"2023071709111493200_ref20","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1002\/net.20435","article-title":"Approximation algorithms for distance constrained vehicle routing problems","volume":"59","author":"Nagarajan","year":"2012","journal-title":"Network"},{"key":"2023071709111493200_ref21","first-page":"744","volume-title":"Proc. of the 46th Annual Symposium on Theory of Computing","author":"Friggstad","year":"2014"},{"key":"2023071709111493200_ref22","first-page":"216","volume-title":"17th Annual Symposium on Foundations of Computer Science","author":"Frederickson","year":"1976"},{"key":"2023071709111493200_ref23","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.tcs.2016.01.041","article-title":"Improved approximation algorithms for some min-max and minimum cycle cover problems","volume":"654","author":"Yu","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"2023071709111493200_ref24","doi-asserted-by":"crossref","first-page":"790","DOI":"10.1287\/opre.40.4.790","article-title":"On the distance constrained vehicle routing problem","volume":"40","author":"Li","year":"1992","journal-title":"Oper. Res."},{"key":"2023071709111493200_ref25","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.tcs.2019.04.009","article-title":"New approximation algorithms for the minimum cycle cover problem","volume":"793","author":"Yu","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"2023071709111493200_ref26","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0377-2217(92)90192-C","article-title":"The vehicle routing problem: An overview of exact and approximate algorithms","volume":"59","author":"Laporte","year":"1992","journal-title":"Eur. J. Oper. Res."},{"key":"2023071709111493200_ref27","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/s10846-016-0458-5","article-title":"Algorithms for heterogeneous, multiple depot, multiple unmanned vehicle path planning problems","volume":"88","author":"Sundar","year":"2017","journal-title":"J. Intell. Robot. Syst."},{"key":"2023071709111493200_ref28","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/j.orl.2003.11.010","article-title":"Min-max tree covers of graphs","volume":"32","author":"Even","year":"2004","journal-title":"Oper. Res. Lett."},{"key":"2023071709111493200_ref29","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.ipl.2007.06.012","article-title":"Approximating the minmax rooted-tree cover in a tree","volume":"104","author":"Nagamochi","year":"2007","journal-title":"Inf. Process. Lett."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/7\/1586\/50876211\/bxac028.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/7\/1586\/50876211\/bxac028.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T09:16:16Z","timestamp":1689585376000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/7\/1586\/6555407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,29]]},"references-count":29,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,3,29]]},"published-print":{"date-parts":[[2023,7,13]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac028","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2023,7]]},"published":{"date-parts":[[2022,3,29]]}}}