{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T14:09:14Z","timestamp":1768918154017,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,4,30]],"date-time":"2023-04-30T00:00:00Z","timestamp":1682812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,30]],"date-time":"2023-04-30T00:00:00Z","timestamp":1682812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971146"],"award-info":[{"award-number":["11971146"]}],"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":[[2023,5]]},"DOI":"10.1007\/s10878-023-01029-2","type":"journal-article","created":{"date-parts":[[2023,4,30]],"date-time":"2023-04-30T11:01:42Z","timestamp":1682852502000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An approximation algorithm for the clustered path travelling salesman problem"],"prefix":"10.1007","volume":"45","author":[{"given":"Jiaxuan","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suogang","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Hou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6872-3315","authenticated-orcid":false,"given":"Wen","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,30]]},"reference":[{"issue":"5","key":"1029_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2818310","volume":"62","author":"HC An","year":"2015","unstructured":"An HC, Kleinberg R, Shmoys DB (2015) Improving Christofides algorithm for the s-t path TSP. J ACM 62(5):1\u201328","journal-title":"J ACM"},{"key":"1029_CR2","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0167-6377(98)00046-7","volume":"24","author":"S Anily","year":"1999","unstructured":"Anily S, Bramel J, Hertz A (1999) A 5\/3-approximation algorithm for the clustered traveling salesman tour and path problems. Oper Res Lett 24:29\u201335","journal-title":"Oper Res Lett"},{"key":"1029_CR3","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/(SICI)1097-0037(199707)29:4<205::AID-NET3>3.0.CO;2-J","volume":"29","author":"EM Arkin","year":"1994","unstructured":"Arkin EM, Hassin R, Klein L (1994) Restricted delivery problems on a network. Networks 29:205\u2013216","journal-title":"Networks"},{"issue":"3","key":"1029_CR4","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0167-6377(89)90037-0","volume":"8","author":"RG Bland","year":"1989","unstructured":"Bland RG, Shallcross DF (1989) Large travelling salesman problems arising from experiments in X-ray crystallography: a preliminary report on computation. Oper Res Lett 8(3):125\u2013128","journal-title":"Oper Res Lett"},{"key":"1029_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0305-0548(75)90015-5","volume":"2","author":"JA Chisman","year":"1975","unstructured":"Chisman JA (1975) The clustered traveling salesman problem. Comput Oper Res 2:115\u2013119","journal-title":"Comput Oper Res"},{"key":"1029_CR6","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"},{"key":"1029_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph theory","author":"R Diestel","year":"2017","unstructured":"Diestel R (2017) Graph theory. Springer, New York"},{"key":"1029_CR8","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Paths, trees and flowers. Can J Math 17:449\u2013467","journal-title":"Can J Math"},{"issue":"2","key":"1029_CR9","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. SIAM J Comput 7(2):178\u2013193","journal-title":"SIAM J Comput"},{"key":"1029_CR10","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1016\/0305-0548(95)00036-4","volume":"23","author":"M Gendreau","year":"1996","unstructured":"Gendreau M, Hertz A, Laporte G (1996) The traveling salesman problem with backhauls. Comput Oper Res 23:501\u2013508","journal-title":"Comput Oper Res"},{"key":"1029_CR11","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s10107-017-1202-z","volume":"172","author":"C Gottschalk","year":"2018","unstructured":"Gottschalk C, Vygen J (2018) Better s-t-tours by Gao trees. Math Program 172:191\u2013207","journal-title":"Math Program"},{"key":"1029_CR12","unstructured":"Grinman A (2015) The Hungarian algorithm for weighted bipartite graphs. Seminar in Theoretical Computer Science"},{"key":"1029_CR13","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF01586932","volume":"51","author":"M Gr\u00f6tschel","year":"1991","unstructured":"Gr\u00f6tschel M, Holland O (1991) Solution of large-scale symmetric traveling salesman problems. Math Program 51:141\u2013202","journal-title":"Math Program"},{"key":"1029_CR14","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/s004530010045","volume":"28","author":"N Guttmann-Beck","year":"2000","unstructured":"Guttmann-Beck N, Hassin R, Khuller S, Raghavachari B (2000) Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28:422\u2013437","journal-title":"Algorithmica"},{"key":"1029_CR15","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"JA Hoogeveen","year":"1991","unstructured":"Hoogeveen JA (1991) Analysis of Christofides heuristic: some paths are more difficult than cycles. Oper Res Lett 10:291\u2013295","journal-title":"Oper Res Lett"},{"key":"1029_CR16","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.disc.2014.04.018","volume":"330","author":"YM Hong","year":"2014","unstructured":"Hong YM, Lai HJ, Liu QH (2014) Supereulerian digraphs. Discret Math 330:87\u201395","journal-title":"Discret Math"},{"issue":"4","key":"1029_CR17","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1287\/opre.1120.1075","volume":"60","author":"EU Jacobson","year":"2012","unstructured":"Jacobson EU, Argon NT, Ziya S (2012) Priority assignment in emergency response. Oper Res 60(4):813\u2013832","journal-title":"Oper Res"},{"key":"1029_CR18","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/0377-2217(85)90309-1","volume":"19","author":"K Jongens","year":"1985","unstructured":"Jongens K, Volgenant T (1985) The symmetric clustered traveling salesman problem. Eur J Oper Res 19:68\u201375","journal-title":"Eur J Oper Res"},{"issue":"2","key":"1029_CR19","first-page":"60","volume":"63","author":"M Kawasaki","year":"2020","unstructured":"Kawasaki M, Takazawa T (2020) Improving approximation ratios for the clustered travelling salesman problem. J Oper Res Soc Jpn 63(2):60\u201370","journal-title":"J Oper Res Soc Jpn"},{"key":"1029_CR20","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1287\/opre.35.5.772","volume":"35","author":"RD Plante","year":"1987","unstructured":"Plante RD, Lowe TJ, Chandrasekaran R (1987) The product matrix travelling salesman problem: An Application and Solution Heuristics. Oper Res 35:772\u2013783","journal-title":"Oper Res"},{"key":"1029_CR21","doi-asserted-by":"crossref","unstructured":"Seb\u0151 A, van Zuylen A (2016) The salesmans improved paths: A 3\/2+1\/34 approximation. In: Proceedings of 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp 118\u2013127","DOI":"10.1109\/FOCS.2016.21"},{"issue":"2","key":"1029_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3309715","volume":"66","author":"V Traub","year":"2019","unstructured":"Traub V, Vygen J (2019) Approaching 3\/2 for the s-t path TSP. J ACM 66(2):1\u201317","journal-title":"J ACM"},{"issue":"1","key":"1029_CR23","doi-asserted-by":"publisher","first-page":"32","DOI":"10.3141\/2378-04","volume":"2378","author":"X Yang","year":"2013","unstructured":"Yang X, Feng L (2013) Inventory routing problem: routing and scheduling approach with the objective of slack maximization. Transp Res Rec 2378(1):32\u201342","journal-title":"Transp Res Rec"},{"key":"1029_CR24","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0020-0190(75)90056-3","volume":"4","author":"A Yao","year":"1975","unstructured":"Yao A (1975) An O$$(\\left|E\\right|\\log \\log \\left|V\\right|)$$ algorithm for finding minimum spanning trees. Inform Process Lett 4:21\u201323","journal-title":"Inform Process Lett"},{"key":"1029_CR25","doi-asserted-by":"crossref","unstructured":"Zenklusen R (2019) A 1.5-approximation for path TSP. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1539\u20131549","DOI":"10.1137\/1.9781611975482.93"},{"key":"1029_CR26","doi-asserted-by":"publisher","first-page":"1573","DOI":"10.1007\/s10479-018-3089-3","volume":"283","author":"L Zhu","year":"2019","unstructured":"Zhu L, Gong Y, Xu Y, Gu J (2019) Emergency relief routing models for injured victims considering equity and priority. Ann Oper Res 283:1573\u20131606","journal-title":"Ann Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01029-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-023-01029-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01029-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,27]],"date-time":"2023-05-27T03:41:26Z","timestamp":1685158886000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-023-01029-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,30]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1029"],"URL":"https:\/\/doi.org\/10.1007\/s10878-023-01029-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,30]]},"assertion":[{"value":"3 April 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"104"}}