{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:41Z","timestamp":1740122381621,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,6,25]],"date-time":"2021-06-25T00:00:00Z","timestamp":1624579200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,25]],"date-time":"2021-06-25T00:00:00Z","timestamp":1624579200000},"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":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007847","name":"Natural Science Foundation of Jilin Province","doi-asserted-by":"publisher","award":["11771386,11728104","11871280"],"award-info":[{"award-number":["11771386,11728104","11871280"]}],"id":[{"id":"10.13039\/100007847","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["06446"],"award-info":[{"award-number":["06446"]}],"id":[{"id":"10.13039\/501100000038","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":[[2022,11]]},"DOI":"10.1007\/s10878-021-00772-8","type":"journal-article","created":{"date-parts":[[2021,6,25]],"date-time":"2021-06-25T18:02:47Z","timestamp":1624644167000},"page":"2499-2514","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation algorithms with constant ratio for general cluster routing problems"],"prefix":"10.1007","volume":"44","author":[{"given":"Xiaoyan","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[]},{"given":"Gregory","family":"Gutin","sequence":"additional","affiliation":[]},{"given":"Qiaoxia","family":"Ming","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4205-9513","authenticated-orcid":false,"given":"Jian","family":"Sun","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,25]]},"reference":[{"issue":"5","key":"772_CR1","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/2818310","volume":"62","author":"H-C An","year":"2015","unstructured":"An H-C, Kleinberg R, Shmoys D-B (2015) Improving Christofides\u2019 algorithm for the $$s$$-$$t$$ path TSP. J ACM 62(5):34","journal-title":"J ACM"},{"issue":"1\u20132","key":"772_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-D, Hertz A (1999) A 5\/3-approximation algorithm for the clustered traveling salesman tour and path problems. Oper Res Lett 24(1\u20132):29\u201335","journal-title":"Oper Res Lett"},{"key":"772_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":"E Arkin","year":"1997","unstructured":"Arkin E, Hassin R, Klein L (1997) Restricted delivery problems on a network. Networks 29:205\u2013216","journal-title":"Networks"},{"key":"772_CR4","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D Bienstock","year":"1991","unstructured":"Bienstock D, Goemans M-X, Simchi D, Williamson D-P (1991) A note on the prize-collecting traveling salesman problem. Math Program 59:413\u2013420","journal-title":"Math Program"},{"key":"772_CR5","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group"},{"key":"772_CR6","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/322139.322150","volume":"26","author":"G-N Frederickson","year":"1979","unstructured":"Frederickson G-N (1979) Approximation algorithms for some postman problems. J ACM 26:538\u2013554","journal-title":"J ACM"},{"key":"772_CR7","first-page":"39","volume":"13","author":"L Fumei","year":"2008","unstructured":"Fumei L, Alantha N (2008) Traveling salesman path problems. Math Progrom 13:39\u201359","journal-title":"Math Progrom"},{"issue":"3","key":"772_CR8","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/net.3230070303","volume":"7","author":"B-L Golden","year":"2010","unstructured":"Golden B-L (2010) A statistical approach to the TSP. Networks 7(3):209\u2013225","journal-title":"Networks"},{"key":"772_CR9","volume-title":"The traveling salesman problem and its variations","author":"G Gutin","year":"2002","unstructured":"Gutin G, Punnen A (2002) The traveling salesman problem and its variations. Kluwer, Dordrecht"},{"issue":"1\u20133","key":"772_CR10","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0166-218X(01)00195-0","volume":"117","author":"G Gutin","year":"2002","unstructured":"Gutin G, Yeo A, Zverovich A (2002) Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Appl Math 117(1\u20133):81\u201386","journal-title":"Discrete Appl Math"},{"key":"772_CR11","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":"772_CR12","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"J-A Hoogeveen","year":"1991","unstructured":"Hoogeveen J-A (1991) Analysis of Christofides\u2019 heuristic: some paths are more difficult than cycles. Oper Res Lett 10:291\u2013295","journal-title":"Oper Res Lett"},{"key":"772_CR13","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0020-0190(92)90161-N","volume":"41","author":"K Jansen","year":"1992","unstructured":"Jansen K (1992) An approximation algorithm for the general routing problem. Inf Process Lett 41:333\u2013339","journal-title":"Inf Process Lett"},{"key":"772_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume":"2","author":"R-M Karp","year":"1972","unstructured":"Karp R-M (1972) Reducibility among combinatorial problems. Complex Comput Comput 2:85\u2013103","journal-title":"Complex Comput Comput"},{"issue":"2","key":"772_CR15","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Lin","year":"1973","unstructured":"Lin S, Kernighan B-W (1973) An effective heuristic algorithm for the traveling salesman problem. Oper Res 21(2):498\u2013516","journal-title":"Oper Res"},{"key":"772_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01902503","volume":"28","author":"L Lov\u00e1sz","year":"1976","unstructured":"Lov\u00e1sz L (1976) On some connectivity properties of Eulerian multigraphs. Atca Math Acad Sci Hung 28:129\u2013138","journal-title":"Atca Math Acad Sci Hung"},{"issue":"1","key":"772_CR17","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/2739008","volume":"63","author":"T M\u00f6mke","year":"2016","unstructured":"M\u00f6mke T, Svensson O (2016) Removing and adding edges for the traveling salesman problem. J ACM 63(1):2","journal-title":"J ACM"},{"key":"772_CR18","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1007\/s00224-012-9439-7","volume":"55","author":"M Mucha","year":"2014","unstructured":"Mucha M (2014) 13\/9-approximation for graphic TSP. Theory Comput Syst 55:640\u2013657","journal-title":"Theory Comput Syst"},{"issue":"2","key":"772_CR19","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00453-002-0986-1","volume":"35","author":"A Punnen","year":"2003","unstructured":"Punnen A, Kabadi M-S (2003) TSP heuristics: domination analysis and complexity. Algorithmica 35(2):111\u2013127","journal-title":"Algorithmica"},{"issue":"3","key":"772_CR20","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni S, Gonzales T (1976) $$P$$-complete approximation problems. J ACM 23(3):555\u2013565","journal-title":"J ACM"},{"key":"772_CR21","doi-asserted-by":"publisher","first-page":"123C134","DOI":"10.1007\/BF02592020","volume":"36","author":"A Seb\u00f6","year":"1986","unstructured":"Seb\u00f6 A (1986) Finding thet-join structure of graphs. Math Program 36:123C134","journal-title":"Math Program"},{"key":"772_CR22","doi-asserted-by":"crossref","unstructured":"Seb\u00f6 A (2013) Eight fifth approximation for TSP paths. In: Goemans M, Correa J (eds) Integer Programming and Combinatorial Optimization 2013, LNCS, vol 7801. Springer. Berlin, Heidelberg, pp 362\u2013374","DOI":"10.1007\/978-3-642-36694-9_31"},{"issue":"4","key":"772_CR23","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/3326123","volume":"66","author":"A Seb\u00f6","year":"2019","unstructured":"Seb\u00f6 A, Van Zuylen A (2019) The salesman\u2019s improved paths through forests. J ACM 66(4):28","journal-title":"J ACM"},{"issue":"5","key":"772_CR24","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","volume":"34","author":"A Seb\u00f6","year":"2014","unstructured":"Seb\u00f6 A, Vygen J (2014) Shorter tours by nicer ears: 7\/5-approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica 34(5):597\u2013629","journal-title":"Combinatorica"},{"key":"772_CR25","doi-asserted-by":"crossref","unstructured":"Traub V, Vygen J (2018) Beating the integrality ratio for $$s$$-$$t$$-tours in graphs. In: Proceedings of 59th annual symposium on foundations of computer science, pp 766\u2013777","DOI":"10.1109\/FOCS.2018.00078"},{"issue":"2","key":"772_CR26","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/3309715","volume":"66","author":"V Traub","year":"2019","unstructured":"Traub V, Vygen J (2019) Approaching $$\\frac{3}{2}$$ for the $$s$$-$$t$$ path TSP. J ACM 66(2):14","journal-title":"J ACM"},{"key":"772_CR27","doi-asserted-by":"crossref","unstructured":"Zenklusen R-A (2019) $$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":"772_CR28","doi-asserted-by":"publisher","unstructured":"Zhang X, Du D, Gutin G, Ming Q, Sun J (2020) Approximation algorithms for general cluster routing problem. In: Kim D., Uma R., Cai Z., Lee D. (eds) Computing and combinatorics. COCOON 2020. Lecture notes in computer science, vol 12273. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-030-58150-3_38","DOI":"10.1007\/978-3-030-58150-3_38"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00772-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00772-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00772-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:19:15Z","timestamp":1665778755000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00772-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,25]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["772"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00772-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,6,25]]},"assertion":[{"value":"9 June 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}