{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T01:15:58Z","timestamp":1777338958148,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:00:00Z","timestamp":1616457600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:00:00Z","timestamp":1616457600000},"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":["71601152"],"award-info":[{"award-number":["71601152"]}],"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":["71732006"],"award-info":[{"award-number":["71732006"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010031","name":"Postdoctoral Research Foundation of China","doi-asserted-by":"publisher","award":["2016M592811"],"award-info":[{"award-number":["2016M592811"]}],"id":[{"id":"10.13039\/501100010031","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Natural Science Basic Research Program of Shaanxi","award":["2020JQ-654"],"award-info":[{"award-number":["2020JQ-654"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72071157"],"award-info":[{"award-number":["72071157"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s10878-021-00720-6","type":"journal-article","created":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T11:03:47Z","timestamp":1616497427000},"page":"844-860","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The m-Steiner Traveling Salesman Problem with online edge blockages"],"prefix":"10.1007","volume":"41","author":[{"given":"Henan","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huili","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"issue":"1","key":"720_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2005.01.007","volume":"59","author":"EM Arkin","year":"2006","unstructured":"Arkin EM, Hassin R, Levin A (2006) Approximations for minimum and min-max vehicle routing problems. J Algorithms 59(1):1\u201318","journal-title":"J Algorithms"},{"issue":"3","key":"720_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","volume":"34","author":"T Bektas","year":"2006","unstructured":"Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3):209\u2013219","journal-title":"Omega"},{"key":"720_CR3","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University"},{"issue":"4","key":"720_CR4","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/j.orl.2003.11.010","volume":"32","author":"G Even","year":"2004","unstructured":"Even G, Garg N, K\u00f6Nemann J, Ravi R, Sinha A (2004) Min-max tree covers of graphs. Oper Res Lett 32(4):309\u2013315","journal-title":"Oper Res Lett"},{"issue":"2","key":"720_CR5","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/0207017","volume":"7","author":"GN Frederickson","year":"1978","unstructured":"Frederickson GN, Hecht MS, Kim CE (1978) Approximation algorithms for some routing problems. SAIM J Comput 7(2):178\u2013193","journal-title":"SAIM J Comput"},{"key":"720_CR6","unstructured":"Garey M and Johnson D (1979) Computers And Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco"},{"issue":"5","key":"720_CR7","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1287\/opre.34.5.698","volume":"34","author":"B Gavish","year":"1986","unstructured":"Gavish B, Srikanth K (1986) An optimal solution method for large-scale multiple traveling salesmen problems. Oper Res 34(5):698\u2013717","journal-title":"Oper Res"},{"issue":"2","key":"720_CR8","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0166-218X(86)90087-9","volume":"13","author":"AA Iqbal","year":"1986","unstructured":"Iqbal AA, Kennington JL (1986) The asymmetric m -travelling salesmen problem: A duality based branch-and-bound algorithm. Discrete Appl Math 13(2):259\u2013276","journal-title":"Discrete Appl Math"},{"issue":"2","key":"720_CR9","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s00453-012-9740-5","volume":"69","author":"MR Khani","year":"2014","unstructured":"Khani MR, Salavatipour MR (2014) Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica 69(2):443\u2013460","journal-title":"Algorithmica"},{"issue":"1","key":"720_CR10","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/0377-2217(85)90284-X","volume":"20","author":"RV Kulkarni","year":"1985","unstructured":"Kulkarni RV, Bhave PR (1985) Integer programming formulations of vehicle routing problems. Eur J Oper Res 20(1):58\u201367","journal-title":"Eur J Oper Res"},{"issue":"11","key":"720_CR11","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1057\/jors.1980.188","volume":"31","author":"G Laporte","year":"1980","unstructured":"Laporte G, Nobert Y (1980) A cutting planes algorithm for the m -salesmen problem. J Oper Res Soc 31(11):1017\u20131023","journal-title":"J Oper Res Soc"},{"key":"720_CR12","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2014.02.026","volume":"530","author":"C-S Liao","year":"2014","unstructured":"Liao C-S, Huang Y (2014) The covering canadian traveller problem. Theor Comput Sci 530:80\u201388","journal-title":"Theor Comput Sci"},{"issue":"6","key":"720_CR13","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1016\/j.orl.2007.02.001","volume":"35","author":"W Malik","year":"2007","unstructured":"Malik W, Rathinam S, Darbha S (2007) An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem. Oper Res Lett 35(6):747\u2013753","journal-title":"Oper Res Lett"},{"issue":"5","key":"720_CR14","doi-asserted-by":"publisher","first-page":"1335","DOI":"10.1093\/ietfec\/e88-a.5.1335","volume":"88","author":"H Nagamochi","year":"2005","unstructured":"Nagamochi H (2005) Approximating the minmax rooted-subtree cover problem. IEICE Trans Fundam Electron Commun Comput Sci 88(5):1335\u20131338","journal-title":"IEICE Trans Fundam Electron Commun Comput Sci"},{"key":"720_CR15","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1988","unstructured":"Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization. Wiley-Interscience, New York, NY, USA"},{"issue":"1","key":"720_CR16","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou CH, Yannakakis M (1991) Shortest paths without a map. Theor Comput Sci 84(1):127\u2013150","journal-title":"Theor Comput Sci"},{"issue":"1","key":"720_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou CH, Yannakakis M (1993) The traveling salesperson problem with distances one and two. Math Oper Res 18(1):1\u201311","journal-title":"Math Oper Res"},{"issue":"3","key":"720_CR18","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.ipl.2007.10.004","volume":"106","author":"S Westphal","year":"2008","unstructured":"Westphal S (2008) A note on the k-canadian traveller problem. Inf Process Lett 106(3):87\u201389","journal-title":"Inf Process Lett"},{"issue":"2","key":"720_CR19","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10878-008-9156-y","volume":"18","author":"Y Xu","year":"2009","unstructured":"Xu Y, Hu M, Su B, Zhu B, Zhu Z (2009) The canadian traveller problem and its competitive analysis. J Comb Optim 18(2):195\u2013205","journal-title":"J Comb Optim"},{"issue":"3","key":"720_CR20","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1016\/j.ejor.2016.08.054","volume":"257","author":"Z Xu","year":"2017","unstructured":"Xu Z, Rodrigues B (2017) An extension of the christofides heuristic for the generalized multiple depot multiple traveling salesmen problem. Eur J Oper Res 257(3):735\u2013745","journal-title":"Eur J Oper Res"},{"issue":"3","key":"720_CR21","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 (2010) Approximation hardness of minmax tree covers. Oper Res Lett 38(3):169\u2013173","journal-title":"Oper Res Lett"},{"issue":"3","key":"720_CR22","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.orl.2011.03.002","volume":"39","author":"Z Xu","year":"2011","unstructured":"Xu Z, Xu L, Rodrigues B (2011) An analysis of the extended christofides heuristic for the k-depot tsp. Oper Res Lett 39(3):218\u2013223","journal-title":"Oper Res Lett"},{"key":"720_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.tcs.2016.01.041","volume":"654","author":"W Yu","year":"2016","unstructured":"Yu W, Liu Z (2016) Improved approximation algorithms for some min-max and minimum cycle cover problems. Theor Comput Sci 654:45\u201358","journal-title":"Theor Comput Sci"},{"issue":"2","key":"720_CR24","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/j.ejor.2018.08.017","volume":"273","author":"H Zhang","year":"2019","unstructured":"Zhang H, Tong W, Lin G, Xu Y (2019) Online minimum latency problem with edge uncertainty. Eur J Oper Res 273(2):418\u2013429","journal-title":"Eur J Oper Res"},{"issue":"1","key":"720_CR25","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.ejor.2014.11.013","volume":"243","author":"H Zhang","year":"2015","unstructured":"Zhang H, Tong W, Xu Y, Lin G (2015) The steiner traveling salesman problem with online edge blockages. Eur J Oper Res 243(1):30\u201340","journal-title":"Eur J Oper Res"},{"key":"720_CR26","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.cor.2015.12.013","volume":"70","author":"H Zhang","year":"2016","unstructured":"Zhang H, Tong W, Xu Y, Lin G (2016) The steiner traveling salesman problem with online advanced edge blockages. Comput Oper Res 70:26\u201338","journal-title":"Comput Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00720-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00720-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00720-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,26]],"date-time":"2021-05-26T05:05:09Z","timestamp":1622005509000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00720-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,23]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["720"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00720-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,23]]},"assertion":[{"value":"2 March 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}