{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:02:27Z","timestamp":1746331347309,"version":"3.40.4"},"publisher-location":"Singapore","reference-count":28,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819644476","type":"print"},{"value":"9789819644483","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-981-96-4448-3_3","type":"book-chapter","created":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T05:50:38Z","timestamp":1746251438000},"page":"26-35","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Approximation Algorithm for\u00a0the\u00a0(Metric) Clustered Path Traveling Salesman Problem"],"prefix":"10.1007","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"}]},{"given":"Wen","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,4]]},"reference":[{"issue":"5","key":"3_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2818310","volume":"62","author":"HC An","year":"2015","unstructured":"An, H.C., Kleinberg, R., Shmoys, D.B.: Improving Christofides\u2019 algorithm for the s-t path TSP. J. ACM 62(5), 1\u201328 (2015)","journal-title":"J. ACM"},{"key":"3_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.: A 5\/3-approximation algorithm for the clustered traveling salesman tour and path problems. Oper. Res. Lett. 24, 29\u201335 (1999)","journal-title":"Oper. Res. Lett."},{"key":"3_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, E.M., Hassin, R., Klein, L.: Restricted delivery problems on a network. Networks 29, 205\u2013216 (1994)","journal-title":"Networks"},{"issue":"3","key":"3_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, R.G., Shallcross, D.F.: Large travelling salesman problems arising from experiments in X-ray crystallography: a preliminary report on computation. Oper. Res. Lett. 8(3), 125\u2013128 (1989)","journal-title":"Oper. Res. Lett."},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Blauth, J., N\u00e4gele, M.: An improved approximation guarantee for prize-collecting TSP. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pp. 1848\u20131861. ACM, New York (2023)","DOI":"10.1145\/3564246.3585159"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0305-0548(75)90015-5","volume":"2","author":"JA Chisman","year":"1975","unstructured":"Chisman, J.A.: The clustered traveling salesman problem. Comput. Oper. Res. 2, 115\u2013119 (1975)","journal-title":"Comput. Oper. Res."},{"key":"3_CR7","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)"},{"key":"3_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. Springer, New York (2017)"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"issue":"2","key":"3_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(2), 178\u2013193 (1978)","journal-title":"SIAM J. Comput."},{"key":"3_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco (1979)"},{"key":"3_CR12","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.: The traveling salesman problem with backhauls. Comput. Oper. Res. 23, 501\u2013508 (1996)","journal-title":"Comput. Oper. Res."},{"key":"3_CR13","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.: Better s-t-tours by Gao trees. Math. Program. 172, 191\u2013207 (2018)","journal-title":"Math. Program."},{"key":"3_CR14","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.: Solution of large-scale symmetric traveling salesman problems. Math. Program. 51, 141\u2013202 (1991)","journal-title":"Math. Program."},{"key":"3_CR15","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.: Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28, 422\u2013437 (2000)","journal-title":"Algorithmica"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"JA Hoogeveen","year":"1991","unstructured":"Hoogeveen, J.A.: Analysis of Christofides\u2019 heuristic: some paths are more difficult than cycles. Oper. Res. Lett. 10, 291\u2013295 (1991)","journal-title":"Oper. Res. Lett."},{"key":"3_CR17","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.: The symmetric clustered traveling salesman problem. Eur. J. Oper. Res. 19, 68\u201375 (1985)","journal-title":"Eur. J. Oper. Res."},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., Gharan, S.O.: An improved approximation algorithm for TSP in the half integral case. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 28\u201339. ACM, New York (2019)","DOI":"10.1145\/3357713.3384273"},{"issue":"2","key":"3_CR19","first-page":"60","volume":"63","author":"M Kawasaki","year":"2020","unstructured":"Kawasaki, M., Takazawa, T.: Improving approximation ratios for the clustered travelling salesman problem. J. Oper. Res. Soc. Jpn. 63(2), 60\u201370 (2020)","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1287\/opre.35.5.772","volume":"35","author":"RD Plante","year":"1987","unstructured":"Plante, R.D., Lowe, T.J., Chandrasekaran, R.: The product matrix travelling salesman problem: an application and solution heuristics. Oper. Res. 35, 772\u2013783 (1987)","journal-title":"Oper. Res."},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Seb\u0151, A., Zuylen, A.V.: The salesman\u2019s improved paths: A 3\/2+1\/34 approximation. In: Proceedings of 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 118\u2013127. IEEE, New Brunswick (2016)","DOI":"10.1109\/FOCS.2016.21"},{"issue":"6","key":"3_CR22","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"DB Shmoys","year":"1990","unstructured":"Shmoys, D.B., Williamson, D.P.: Analyzing the Held-Karp TSP bound: a monotonicity property with application. Inf. Process. Lett. 35(6), 281\u2013285 (1990)","journal-title":"Inf. Process. Lett."},{"key":"3_CR23","first-page":"76","volume":"17","author":"A Serdjukov","year":"1978","unstructured":"Serdjukov, A.: Some extremal bypasses in graphs. Upr Sist 17, 76\u201379 (1978)","journal-title":"Upr Sist"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.tcs.2022.11.013","volume":"941","author":"J Sun","year":"2023","unstructured":"Sun, J., Gutin, G., Li, P., Shi, P., Zhang, X.: An LP-based approximation algorithm for the generalized traveling salesman path problem. Theor. Comput. Sci. 941, 180\u2013190 (2023)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"3_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3309715","volume":"66","author":"V Traub","year":"2019","unstructured":"Traub, V., Vygen, J.: Approaching $$3\/2$$ for the $$s$$-$$t$$ path TSP. J. ACM 66(2), 1\u201317 (2019)","journal-title":"J. ACM"},{"key":"3_CR26","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.: An $$O(\\left|E\\right|\\log \\log \\left|V\\right|)$$ algorithm for finding minimum spanning trees. Inf. Process. Lett. 4, 21\u201323 (1975)","journal-title":"Inf. Process. Lett."},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Zenklusen, R.: A 1.5-approximation for path TSP. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1539\u20131549. SIAM, San Diego (2019)","DOI":"10.1137\/1.9781611975482.93"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/s10878-023-01029-2","volume":"45","author":"JX Zhang","year":"2023","unstructured":"Zhang, J.X., Gao, S.G., Hou, B., Liu, W.: An approximation algorithm for the clustered path traveling salesman problem. J. Comb. Optim. 45, 104 (2023)","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-4448-3_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T05:50:43Z","timestamp":1746251443000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-4448-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819644476","9789819644483"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-4448-3_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"4 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure Interests"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","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":"6 December 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.cocoa2024.com\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}