{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:21:35Z","timestamp":1759335695729,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":26,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819778003"},{"type":"electronic","value":"9789819778010"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-981-97-7801-0_9","type":"book-chapter","created":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T18:05:37Z","timestamp":1726769137000},"page":"99-110","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved Approximation Algorithms for\u00a0Patrol-Scheduling with\u00a0Min-Max Latency Using Multiclass Minimum Spanning Forests"],"prefix":"10.1007","author":[{"given":"Li-Hsuan","family":"Chen","sequence":"first","affiliation":[]},{"given":"Ling-Ju","family":"Hung","sequence":"additional","affiliation":[]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"key":"9_CR1","series-title":"Springer Proceedings in Advanced Robotics","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-030-66723-8_7","volume-title":"Algorithmic Foundations of Robotics XIV","author":"P Afshani","year":"2021","unstructured":"Afshani, P., et al.: Approximation algorithms for multi-robot patrol-scheduling with min-max latency. In: LaValle, S.M., Lin, M., Ojala, T., Shell, D., Yu, J. (eds.) WAFR 2020. SPAR, vol. 17, pp. 107\u2013123. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-66723-8_7"},{"key":"9_CR2","unstructured":"Afshani, P., et al.: On cyclic solutions to the min-max latency multi-robot patrolling problem. In: Goaoc, X., Kerber, M. (eds.) Proceedings of the 38th International Symposium on Computational Geometry (SoCG\u00a02022), pp.\u00a02:1\u20132:14 (2022). Article No. 2"},{"key":"9_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. Rob. Res. 33, 138\u2013154 (2014)","journal-title":"Int. J. Rob. Res."},{"key":"9_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\u201318 (2006)","journal-title":"J. Algorithms"},{"key":"9_CR5","series-title":"Springer Proceedings in Advanced Robotics","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1007\/978-3-030-43089-4_47","volume-title":"Algorithmic Foundations of Robotics XII","author":"C Baykal","year":"2020","unstructured":"Baykal, C., Rosman, G., Kotowick, K., Donahue, M., Rus, D.: Persistent surveillance of events with unknown rate statistics. In: Algorithmic Foundations of Robotics XII. SPAR, vol. 13, pp. 736\u2013751. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-43089-4_47"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"B\u00e9rczi, K., Mnich, M., Vincze, R.: Approximations for many-visits multiple traveling salesman problems. Omega 116, 102816","DOI":"10.1016\/j.omega.2022.102816"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1023\/A:1016639210559","volume":"31","author":"H Choset","year":"2001","unstructured":"Choset, H.: Coverage for robotics-a survey of recent results. Ann. Math. Artif. Intell. 31, 113\u2013126 (2001)","journal-title":"Ann. Math. Artif. Intell."},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1002\/net.3230140205","volume":"14","author":"N Christofides","year":"1984","unstructured":"Christofides, N., Beasley, J.E.: The period routing problem. Networks 14, 237\u2013256 (1984)","journal-title":"Networks"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Oper. Res. Forum 3 (2022). Article number 20","DOI":"10.1007\/s43069-021-00101-z"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/0207017","volume":"7","author":"GN Frederickson","year":"1978","unstructured":"Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. SIAM J. Comput. 7, 178\u2013193 (1978)","journal-title":"SIAM J. Comput."},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0925-7721(02)00110-4","volume":"24","author":"Y Gabriely","year":"2003","unstructured":"Gabriely, Y., Rimon, E.: Competitive on-line coverage of grid environments by a mobile robot. Comput. Geomerty Theory Appl. 24, 197\u2013224 (2003)","journal-title":"Comput. Geomerty Theory Appl."},{"key":"9_CR12","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Co. (1979)"},{"key":"9_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2023.103476","volume":"139","author":"L G\u0105sieniec","year":"2024","unstructured":"G\u0105sieniec, L., et al.: Perpetual maintenance of machines with different urgency requirements. J. Comput. Syst. Sci. 139, 103476 (2024)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1016\/j.ipl.2015.03.011","volume":"115","author":"B Gorain","year":"2015","unstructured":"Gorain, B., Mandal, P.S.: Approximation algorithm for sweep coverage on graph. Inf. Process. Lett. 115, 712\u2013718 (2015)","journal-title":"Inf. Process. Lett."},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1109\/TCST.2007.899155","volume":"15","author":"II Hussein","year":"2007","unstructured":"Hussein, I.I., Stipanovi\u0107, D.M.: Effective coverage control for mobile sensor networks with guaranteed collision avoidance. IEEE Trans. Control Syst. Technol. 15, 642\u2013657 (2007)","journal-title":"IEEE Trans. Control Syst. Technol."},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., Gharan, S.O.: A (slightly) improved approximation algorithm for metric TSP. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u00a02021), pp.\u00a032\u201345 (2021)","DOI":"10.1145\/3406325.3451009"},{"issue":"8","key":"9_CR17","doi-asserted-by":"publisher","first-page":"1665","DOI":"10.1016\/j.jcss.2015.06.003","volume":"81","author":"M Karpinski","year":"2015","unstructured":"Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. J. Comput. Syst. Sci. 81(8), 1665\u20131677 (2015)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR18","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, 443\u2013460 (2014)","journal-title":"Algorithmica"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s10479-014-1648-9","volume":"239","author":"HC Lau","year":"2016","unstructured":"Lau, H.C., Yuan, Z., Gunawan, A.: Patrol scheduling in urban rail network. Ann. Oper. Res. 239, 317\u2013342 (2016)","journal-title":"Ann. Oper. Res."},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Mathew, N., Smith, S.L., Waslander, S.L.: A graph-based approach to multi-robot rendezvous for recharging in persistent task. In: IEEE International Conference on Robotics and Authomation, pp.\u00a03482\u20133487 (2013)","DOI":"10.1109\/ICRA.2013.6631066"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Michael, N., Stump, E., Mohta, K.: Persistent surveillance with a team of MAVs. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp.\u00a02708\u20132714 (2011)","DOI":"10.1109\/IROS.2011.6095174"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1398\u20131401 (1957)","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"9_CR23","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discret. Math. 19, 122\u2013134 (2005)","journal-title":"SIAM J. Discret. Math."},{"key":"9_CR24","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1002\/rob.20405","volume":"28","author":"RN Smith","year":"2011","unstructured":"Smith, R.N., Schwager, M., Smith, S.L., Rus, D., Sukhatme, G.S.: Persistent ocean monitoring with underwater gliders: adapting sampling resolution. J. Field Rob. 28, 714\u2013741 (2011)","journal-title":"J. Field Rob."},{"key":"9_CR25","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, pp.\u00a0569\u2013575 (2011)","DOI":"10.1109\/CASE.2011.6042503"},{"key":"9_CR26","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.orl.2010.02.004","volume":"38","author":"Z Xu","year":"2010","unstructured":"Xu, Z., Wen, Q.: Approximation hardness of min-max tree cover. Oper. Res. Lett. 38, 169\u2013173 (2010)","journal-title":"Oper. Res. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-7801-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T18:08:24Z","timestamp":1726769304000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-7801-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819778003","9789819778010"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-7801-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"19 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Aspects in Information and Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dallas, TX","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/AAIM2024\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}