{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T16:38:20Z","timestamp":1776875900140,"version":"3.51.2"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030667221","type":"print"},{"value":"9783030667238","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-66723-8_7","type":"book-chapter","created":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T13:36:54Z","timestamp":1612877814000},"page":"107-123","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency"],"prefix":"10.1007","author":[{"given":"Peyman","family":"Afshani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"de Berg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Buchin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maarten","family":"L\u00f6ffler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Nayyeri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rik","family":"Sarkar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haotian","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao-Tsung","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,9]]},"reference":[{"key":"7_CR1","unstructured":"Abrahamsen, M., de\u00a0Berg, M., Buchin, K., Mehr, M., Mehrabi, A.D.: Range-clustering queries. In: 33rd International Symposium on Computational Geometry (SoCG 2017), pp. 1\u201316, 14\u201317 (2017)"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Afshani, P., de\u00a0Berg, M., Buchin, K., Gao, J., Loffler, M., Nayyeri, A., Raichel, B., Sarkar, R., Wang, H., Yang, H.-T.: Approximation algorithms for multi-robot patrol-scheduling with min-max latency 2020. https:\/\/arxiv.org\/abs\/2005.02530","DOI":"10.1007\/978-3-030-66723-8_7"},{"issue":"1","key":"7_CR3","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1177\/0278364913504011","volume":"33","author":"S Alamdari","year":"2014","unstructured":"Alamdari, S., Fata, E., Smith, S.L.: Persistent monitoring in discrete environments: minimizing the maximum weighted latency between observations. Int. J. Robot. Res. 33(1), 138\u2013154 (2014)","journal-title":"Int. J. Robot. Res."},{"issue":"1","key":"7_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2005.01.007","volume":"59","author":"EM Arkin","year":"2006","unstructured":"Arkin, E.M., Hassin, R., Levin, A.: Approximations for minimum and min-max vehicle routing problems. J. Algorithms 59(1), 1\u201318 (2006)","journal-title":"J. Algorithms"},{"issue":"5","key":"7_CR5","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM (JACM) 45(5), 753\u2013782 (1998)","journal-title":"J. ACM (JACM)"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Asghar, A.B., Smith, S.L., Sundaram, S.: Multi-robot routing for persistent monitoring with latency constraints. In: 2019 American Control Conference (ACC), pp. 2620\u20132625 (2019)","DOI":"10.23919\/ACC.2019.8814485"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"key":"7_CR8","unstructured":"Chevaleyre, Y.: Theoretical analysis of the multi-agent patrolling problem. In: IEEE\/WIC\/ACM International Conference on Intelligent Agent Technology, pp. 302\u2013308 (2004)"},{"key":"7_CR9","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report, Carnegie-Mellon University (1976)"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., G\u0105sieniec, L., Kosowski, A., Kranakis, E.: Boundary patrolling by mobile agents with distinct maximal speeds. In: European Symposium on Algorithms, pp. 701\u2013712 (2011)","DOI":"10.1007\/978-3-642-23719-5_59"},{"issue":"1","key":"7_CR11","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"GB Dantzig","year":"1959","unstructured":"Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80\u201391 (1959)","journal-title":"Manage. Sci."},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Drucker, N., Penn, M., Strichman, O.: Cyclic routing of unmanned aerial vehicles. In: International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pp. 125\u2013141 (2016)","DOI":"10.1007\/978-3-319-33954-2_10"},{"issue":"3","key":"7_CR13","first-page":"3","volume":"21","author":"A Dumitrescu","year":"2014","unstructured":"Dumitrescu, A., Ghosh, A., T\u00f3th, C.D.: On fence patrolling by mobile agents. Electron. J. Comb. 21(3), 3\u20134 (2014)","journal-title":"Electron. J. Comb."},{"issue":"3\u20134","key":"7_CR14","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10472-010-9193-y","volume":"57","author":"Y Elmaliach","year":"2009","unstructured":"Elmaliach, Y., Agmon, N., Kaminka, G.A.: Multi-robot area patrol under frequency constraints. Ann. Math. Artif. Intell. 57(3\u20134), 293\u2013320 (2009)","journal-title":"Ann. Math. Artif. Intell."},{"key":"7_CR15","unstructured":"Elmaliach, Y., Shiloni, A., Kaminka, G.A.: A realistic model of frequency-based multi-robot polyline patrolling. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 63\u201370 (2008)"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"G\u0105sieniec, L., Klasing, R., Levcopoulos, C., Lingas, A., Min, J., Radzik, T.: Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors). In: SOFSEM 2017: Theory and Practice of Computer Science, pp. 229\u2013240 (2017)","DOI":"10.1007\/978-3-319-51963-0_18"},{"key":"7_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-77778-8","volume-title":"The Vehicle Routing Problem: Latest Advances and New Challenges","author":"BL Golden","year":"2008","unstructured":"Golden, B.L., Raghavan, S., Wasil, E.A.: The Vehicle Routing Problem: Latest Advances and New Challenges. Springer Science & Business Media, New York (2008)"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Iocchi, L., Marchetti, L., Nardi, D.: Multi-robot patrolling with coordinated behaviours in realistic environments. In: 2011 IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp. 2796\u20132801, September 2011","DOI":"10.1109\/IROS.2011.6094844"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Kawamura, A., Soejima, M.: Simple strategies versus optimal schedules in multi-agent patrolling. In: International Conference on Algorithms and Complexity, pp. 261\u2013273 (2015)","DOI":"10.1007\/978-3-319-18173-8_19"},{"issue":"1","key":"7_CR20","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1134\/S0081543815050107","volume":"289","author":"MY Khachai","year":"2015","unstructured":"Khachai, M.Y., Neznakhina, E.: A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph. Proc. Steklov Inst. Math. 289(1), 111\u2013125 (2015)","journal-title":"Proc. Steklov Inst. Math."},{"issue":"12","key":"7_CR21","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.ifacol.2016.07.541","volume":"49","author":"M Khachay","year":"2016","unstructured":"Khachay, M., Neznakhina, K.: Polynomial time approximation scheme for the minimum-weight $$k$$-size cycle cover problem in Euclidean space of an arbitrary fixed dimension. IFAC-Papers OnLine 49(12), 6\u201310 (2016)","journal-title":"IFAC-Papers OnLine"},{"issue":"2","key":"7_CR22","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s00453-012-9740-5","volume":"69","author":"MR Khani","year":"2014","unstructured":"Khani, M.R., Salavatipour, M.R.: Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica 69(2), 443\u2013460 (2014)","journal-title":"Algorithmica"},{"key":"7_CR23","first-page":"1","volume":"2017","author":"KS Liu","year":"2017","unstructured":"Liu, K.S., Mayer, T., Yang, H.T., Arkin, E., Gao, J., Goswami, M., Johnson, M.P., Kumar, N., Lin, S.: Joint sensing duty cycle scheduling for heterogeneous coverage guarantee. INFOCOM 2017, 1\u20139 (2017)","journal-title":"INFOCOM"},{"issue":"4","key":"7_CR24","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JS Mitchell","year":"1999","unstructured":"Mitchell, J.S.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, $$k$$-mst, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"7_CR25","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: The Euclidean travelling salesman problem is NP-complete. Theoretical Comput. Sci. 4(3), 237\u2013244 (1977)","journal-title":"Theoretical Comput. Sci."},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Portugal, D., Pippin, C., Rocha, R.P., Christensen, H.: Finding optimal routes for multi-robot patrolling in generic graphs. In: 2014 IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp. 363\u2013369 (2014)","DOI":"10.1109\/IROS.2014.6942585"},{"key":"7_CR27","doi-asserted-by":"crossref","unstructured":"Portugal, D., Rocha, R.P.: On the performance and scalability of multi-robot patrolling algorithms. In: 2011 IEEE International Symposium on Safety, Security, and Rescue Robotics, pp. 50\u201355, November 2011","DOI":"10.1109\/SSRR.2011.6106761"},{"key":"7_CR28","doi-asserted-by":"crossref","unstructured":"Stump, E., Michael, N.: Multi-robot persistent surveillance planning as a vehicle routing problem. In: 2011 IEEE Conference on Automation Science and Engineering (CASE), pp. 569\u2013575, August 2011","DOI":"10.1109\/CASE.2011.6042503"},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D.: The vehicle routing problem. SIAM (2002)","DOI":"10.1137\/1.9780898718515"},{"issue":"3","key":"7_CR30","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1109\/TC.2013.2295609","volume":"64","author":"W Xu","year":"2013","unstructured":"Xu, W., Liang, W., Lin, X.: Approximation algorithms for min-max cycle cover problems. IEEE Trans. Comput. 64(3), 600\u2013613 (2013)","journal-title":"IEEE Trans. Comput."},{"key":"7_CR31","unstructured":"Yang, H.-T., Tsai, S.-Y., Liu, K.S., Lin, S., Gao J.: Patrol scheduling against adversaries with varying attack durations. In: Proceedings of the 18th International Conference on Autonomous Agents and Multi-Agent Systems, pp. 1179\u20131188 (2019)"}],"container-title":["Springer Proceedings in Advanced Robotics","Algorithmic Foundations of Robotics XIV"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-66723-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T15:42:04Z","timestamp":1619278924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-66723-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030667221","9783030667238"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-66723-8_7","relation":{},"ISSN":["2511-1256","2511-1264"],"issn-type":[{"value":"2511-1256","type":"print"},{"value":"2511-1264","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"9 February 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAFR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on the Algorithmic Foundations of Robotics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Oulu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Finland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wafr2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/robotics.cs.rutgers.edu\/wafr2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}