{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:19:25Z","timestamp":1742955565812,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031160806"},{"type":"electronic","value":"9783031160813"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-16081-3_2","type":"book-chapter","created":{"date-parts":[[2022,9,17]],"date-time":"2022-09-17T22:02:24Z","timestamp":1663452144000},"page":"15-27","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Approximation Algorithm for\u00a0the\u00a0Clustered Path Travelling 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":[[2022,9,18]]},"reference":[{"issue":"5","key":"2_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2818310","volume":"62","author":"H-C An","year":"2015","unstructured":"An, H.-C., Kleinberg, R., Shmoys, D.B.: Improving Christofide\u2019 algorithm for the s-t path TSP. J. ACM 62(5), 1\u201328 (2015)","journal-title":"J. ACM"},{"key":"2_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":"2_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":"2_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":"2_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, J.A.: The clustered traveling salesman problem. Comput. Oper. Res. 2, 115\u2013119 (1975)","journal-title":"Comput. Oper. Res."},{"unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the Travelling Salesman Problem. Technical report 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)","key":"2_CR6"},{"key":"2_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.: Graph Theory. Springer, New York (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3"},{"key":"2_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.: Paths, trees and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"2_CR9","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."},{"unstructured":"Grinman, A.: The Hungarian algorithm for weighted bipartite graphs. Seminar in Theoretical Computer Science (2015)","key":"2_CR10"},{"key":"2_CR11","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":"2_CR12","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":"2_CR13","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":"2_CR14","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.disc.2014.04.018","volume":"330","author":"YM Hong","year":"2014","unstructured":"Hong, Y.M., Lai, H.J., Liu, Q.H.: Supereulerian digraphs. Discrete Math. 330, 87\u201395 (2014)","journal-title":"Discrete Math."},{"key":"2_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, 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":"2_CR16","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."},{"issue":"2","key":"2_CR17","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":"2_CR18","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."},{"doi-asserted-by":"crossref","unstructured":"Seb\u0151, A., van Zuylen, A.: 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 (2016)","key":"2_CR19","DOI":"10.1109\/FOCS.2016.21"},{"issue":"2","key":"2_CR20","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":"2_CR21","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."},{"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 (2019)","key":"2_CR22","DOI":"10.1137\/1.9781611975482.93"}],"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-3-031-16081-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,17]],"date-time":"2022-09-17T22:02:37Z","timestamp":1663452157000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-16081-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031160806","9783031160813"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-16081-3_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"18 September 2022","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 Applications in Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 August 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 August 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Springer Nature EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"59","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"69% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}