{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T12:00:07Z","timestamp":1752667207252,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":46,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387747583"},{"type":"electronic","value":"9780387747590"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-74759-0_687","type":"book-chapter","created":{"date-parts":[[2008,8,25]],"date-time":"2008-08-25T11:07:27Z","timestamp":1219662447000},"page":"3935-3944","source":"Crossref","is-referenced-by-count":5,"title":["Traveling Salesman Problem"],"prefix":"10.1007","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"687_CR1_687","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S (1998) Polynomial-time approximation schemes for\nEuclidean TSP and other geometric problems. J ACM 45:753\u2013782","journal-title":"J ACM"},{"key":"687_CR2_687","first-page":"207","volume-title":"The Traveling Salesman Problem and its Variations","author":"S Arora","year":"2002","unstructured":"Arora S (2002) Approximation algorithms for geometric TSP. In:\nGutin G, Punnen AP (eds) The Traveling Salesman Problem and its\nVariations. Kluwer, Dordrecht, pp\u00a0207\u2013221"},{"key":"687_CR3_687","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"J Bang-Jensen","year":"2000","unstructured":"Bang-Jensen J, Gutin G (2000) Digraphs: Theory, Algorithms and Applications. Springer, London"},{"key":"687_CR4_687","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1016\/j.jda.2005.07.004","volume":"4","author":"M Blaeser","year":"2006","unstructured":"Blaeser M, Manthey B, Sgall J (2006) An Improved Approximation Algorithm for the Asymmetric TSP with\nStrengthened Triangle Inequality. J\u00a0Discret Algorithms 4:623\u2013632","journal-title":"J Discret Algorithms"},{"key":"687_CR5_687","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/S0036144596297514","volume":"40","author":"RE Burkard","year":"1998","unstructured":"Burkard RE, Deineko VG, van Dal R, van der Veen JAA,\nWoeginger GJ (1998) Well-solvable special cases of the\ntraveling salesman problem: a\u00a0survey. SIAM Rev 40:496\u2013546","journal-title":"SIAM Rev"},{"key":"687_CR6_687","unstructured":"Baum EB (1986) Iterated descent: A\u00a0better algorithm for local search in\ncombinatorial optimization problems. unpublished manuscript"},{"key":"687_CR7_687","unstructured":"Chekuri C,  Goldberg A, Karger D, Levine M, Stein C (1997) Experimental Study of Minimum Cut\nAlgorithms. In: Proc. 8th ACM-SIAM Symp. Discrete Algorithms (SODA'97).\nACM\/SIAM, pp\u00a0324\u2013333"},{"key":"687_CR8_687","unstructured":"Christofides N (1976) Worst-case analysis of a\u00a0new\nheuristic for the traveling salesman problem. Technical Report CS-93\u201313,\n\t  Carnegie Mellon University"},{"key":"687_CR9_687","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1287\/opre.12.4.568","volume":"12","author":"G Clarke","year":"1964","unstructured":"Clarke G, Wright JW (1964) Scheduling of vehicles from a\u00a0central depot to a\u00a0number of delivery\npoints. Oper Res 12:568\u2013581","journal-title":"Oper Res"},{"key":"687_CR10_687","first-page":"393","volume":"2","author":"GB Dantzig","year":"1954","unstructured":"Dantzig GB, Fulkerson DR, Johnson SM (1954) Solution of\nlarge scale traveling salesman problem. Oper Res 2:393\u2013410","journal-title":"Oper Res"},{"key":"687_CR11_687","first-page":"169","volume-title":"The Traveling Salesman Problem and its Variations","author":"M Fischetti","year":"2002","unstructured":"Fischetti M,  Lodi A, Toth P (2002) \nExact Methods for the Asymmetric Traveling Salesman Problem. In: Gutin G, Punnen AP (eds) \nThe Traveling Salesman Problem and its Variations. \nKluwer, Dordrecht, pp\u00a0169\u2013205"},{"key":"687_CR12_687","doi-asserted-by":"crossref","unstructured":"Garey MR, Graham RL, Johnson DS (1976) Some NP-complete\ngeometric problems. In: Proc. 8th ACM Symp. Theory\n\t  Comput. ACM, pp\u00a010\u201322","DOI":"10.1145\/800113.803626"},{"key":"687_CR13_687","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/S0377-2217(99)00468-3","volume":"129","author":"F Glover","year":"2001","unstructured":"Glover F, Gutin G, Yeo A, Zverovich A (2001) Construction\nheuristics for the asymmetric TSP. Eur J Oper Res 129:555\u2013568","journal-title":"Eur J Oper Res"},{"key":"687_CR14_687","first-page":"207","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"BL Golden","year":"1985","unstructured":"Golden BL, Stewart WR (1985) Empirical Analysis of\nHeuristics. In: Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (eds) The\nTraveling Salesman Problem: A\u00a0Guided Tour of Combinatorial Optimization.\nWiley, New York, pp\u00a0207\u2013249"},{"key":"687_CR15_687","first-page":"13","volume":"8","author":"G Gutin","year":"2005","unstructured":"Gutin G, Jakubowicz H, Ronen S, Zverovitch A (2005)\nSeismic vessel problem. Commun DQM 8:13\u201320","journal-title":"Commun DQM"},{"key":"687_CR16_687","first-page":"52","volume":"1","author":"G Gutin","year":"2006","unstructured":"Gutin G, Koller A, Yeo A (2006) Note on Upper Bounds for TSP\nDomination Number. Algorithmic Oper Res 1:52\u201354","journal-title":"Algorithmic Oper Res"},{"key":"687_CR17_687","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\nshould not be greedy: domination analysis of greedy-type heuristics for the\nTSP. Discrete Appl Math 117:81\u201386","journal-title":"Discrete Appl Math"},{"key":"687_CR18_687","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1006\/jagm.2001.1187","volume":"41","author":"R Hassin","year":"2001","unstructured":"Hassin R, Khuller S (2001) z\u2011Approximations. J\u00a0Algorithms\n41:429\u2013442","journal-title":"J Algorithms"},{"key":"687_CR19_687","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held M, Karp RM (1962) A\u00a0dynamic programming approach to\nsequencing problems. J\u00a0Soc Ind Appl Math 10:196\u2013210","journal-title":"J Soc Ind Appl Math"},{"key":"687_CR20_687","first-page":"1","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"AJ Hoffman","year":"1985","unstructured":"Hoffman AJ, Wolfe P (1985) History. \nIn: Lawler EL, Lenstra\nJK, Rinnooy Kan AHG, Shmoys DB (eds) The Traveling Salesman Problem: A\u00a0Guided\nTour of Combinatorial Optimization. Wiley, New York, pp\u00a01\u201316"},{"key":"687_CR21_687","volume-title":"The Traveling Salesman Problem and its Variations","author":"DS Johnson","year":"2002","unstructured":"Johnson DS, Gutin G, McGeoch LA, Yeo A, Zhang W,\nZverovitch A (2002) Experimental Analysis of Heuristics for ATSP. In: Gutin G,\nPunnen AP (eds) The Traveling Salesman Problem and its Variations. Kluwer,\nDordrecht"},{"key":"687_CR22_687","first-page":"369","volume-title":"The Traveling Salesman Problem and its Variations","author":"DS Johnson","year":"2002","unstructured":"Johnson DS, McGeoch LA (2002) Experimental Analysis of\nHeuristics for STSP. In: Gutin G, Punnen AP (eds) The Traveling Salesman\nProblem and its Variations. Kluwer, Dordrecht, pp\u00a0369\u2013443"},{"key":"687_CR23_687","first-page":"145","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"DS Johnson","year":"1985","unstructured":"Johnson DS, Papadimitriou CH (1985) Performance guarantees\nfor heuristics. In: Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (eds)\nThe Traveling Salesman Problem: A\u00a0Guided Tour of Combinatorial Optimization.\nWiley, New York, pp\u00a0145\u2013180"},{"key":"687_CR24_687","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0167-6377(83)90048-2","volume":"2","author":"R Jonker","year":"1983","unstructured":"Jonker R, Volgenant T (1983) Transforming asymmetric\ninto symmetric traveling salesman problems. Oper Res Lett 2:161\u2013163","journal-title":"Oper Res Lett"},{"key":"687_CR25_687","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/s004539910009","volume":"26","author":"M J\u00fcnger","year":"2000","unstructured":"J\u00fcnger M, Rinaldi G, Thienel S (2000) Practical\nPerformance of efficient minimum Cut Algorithms.  Algorithmica 26:172\u2013195","journal-title":"Algorithmica"},{"key":"687_CR26_687","first-page":"489","volume-title":"The Traveling Salesman Problem and its Variations","author":"SN Kabadi","year":"2002","unstructured":"Kabadi SN\n(2002) Polynomially solvable cases of the TSP. In: Gutin G, Punnen AP (eds)\nThe Traveling Salesman Problem and its Variations. Kluwer, Dordrecht, pp\u00a0489\u2013583"},{"key":"687_CR27_687","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H Kaplan","year":"2005","unstructured":"Kaplan H, Lewenstein M, Shafrir N, Sviridenko M (2005)\nApproximation Algorithms for the Asymmetric TSP by Decomposing Regular\nMultigraphs. J\u00a0ACM 52:602\u2013626","journal-title":"J ACM"},{"key":"687_CR28_687","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial\nproblems. In: Miller RE, Thatcher JW (eds) Complexity of Computer\nComputations. Plenum Press, New York, pp 85\u2013103"},{"key":"687_CR29_687","first-page":"181","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"RM Karp","year":"1985","unstructured":"Karp RM,\nSteele JM (1985) Probabilistic analysis of heuristics. In: Lawler EL, Lenstra\nJK, Rinnooy Kan AHG, Shmoys DB (eds) The Traveling Salesman Problem:\nA\u00a0Guided Tour of Combinatorial Optimization. Wiley, New York, pp\u00a0181\u2013205"},{"key":"687_CR30_687","first-page":"737","volume-title":"The Traveling Salesman Problem and its Variations","author":"A Lodi","year":"2002","unstructured":"Lodi A, Punnen AP (2002) TSP Software. In: Gutin G, Punnen AP\n(eds) The Traveling Salesman Problem and its Variations. Kluwer,\n\t  Dordrecht, pp\u00a0737\u2013749"},{"key":"687_CR31_687","unstructured":"Menger K (1932) Das Botenproblem. Ergebnisse eines\nMathematischen Kolloquiums 2:11\u201312"},{"key":"687_CR32_687","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller CE, Tucker AW, Zemlin RA (1960) Integer\nProgramming formulations and traveling salesman problems. J\u00a0Assoc Comput Mach\n7:326\u2013329","journal-title":"J Assoc Comput Mach"},{"key":"687_CR33_687","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JCB Mitchell","year":"1999","unstructured":"Mitchell JCB (1999) Guillotine subdivisions approximate\npolygonal subdivisions: A\u00a0simple polynomial time approximation scheme for\ngeometric TSP, k-MST, and related problem. SIAM J Comput 28:1298\u20131309","journal-title":"SIAM J Comput"},{"key":"687_CR34_687","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/11844297_38","volume":"4193","author":"Y Nagata","year":"2006","unstructured":"Nagata Y (2006) New EAX crossover for large TSP\ninstances.  Lecture Notes Comp Sci 4193:372\u2013381","journal-title":"Lecture Notes Comp Sci"},{"key":"687_CR35_687","unstructured":"Nagata Y, Kobayashi S (1997) Edge Assembly Crossover: A\u00a0High-power\nGenetic Algorithm for the Traveling Salesman Problem. In: Proc.\nof the 7th Int. Conference on Genetic Algorithms, pp 450\u2013457"},{"key":"687_CR36_687","first-page":"29","volume-title":"The Traveling Salesman Problem and its Variations","author":"D Naddef","year":"2002","unstructured":"Naddef D (2002) Polyhedral Theory and Branch-and-Cut Algorithms\nfor the Symmetric TSP. In: Gutin G, Punnen AP (eds) The Traveling Salesman\nProblem and its Variations. Kluwer, Dordrecht, pp\u00a029\u2013116"},{"key":"687_CR37_687","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01582894","volume":"52","author":"MW Padberg","year":"1991","unstructured":"Padberg MW, Sung TY (1991) An analytical comparison of\ndifferent formulations of the traveling salesman problem. Math Program Ser A\n52:315\u2013357","journal-title":"Math Program Ser A"},{"key":"687_CR38_687","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou CH (1977) The Euclidean traveling salesman\nproblem is NP-complete. Theoret Comput Sci 4:237\u2013244","journal-title":"Theoret Comput Sci"},{"key":"687_CR39_687","volume-title":"Combinatorial Optimization","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou CH, Steiglitz K (1982) Combinatorial\nOptimization. Prentice-Hall, New Jersey"},{"key":"687_CR40_687","first-page":"1","volume-title":"The Traveling Salesman Problem and its Variations","author":"AP Punnen","year":"2002","unstructured":"Punnen AP (2002) The Traveling Salesman Problem: Aplications,\nFormulations and Variations. In: Gutin G, Punnen AP (eds) The Traveling\nSalesman Problem and its Variations. Kluwer, Dordrecht, pp\u00a01\u201328"},{"key":"687_CR41_687","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00453-002-0986-1","volume":"35","author":"AP Punnen","year":"2003","unstructured":"Punnen AP,  Margot F, Kabadi S (2003) TSP heuristics:\ndomination analysis and complexity. Algorithmica 35:111\u2013127","journal-title":"Algorithmica"},{"key":"687_CR42_687","doi-asserted-by":"crossref","unstructured":"Rao S, Smith W (1998) Approximating geometric graphs via\n\u201cspanners\u201d and \u201cbanyans\u201d. Proc. 30th Ann. ACM Symp. Theory\nComput. ACM, pp 540\u2013550","DOI":"10.1145\/276698.276868"},{"key":"687_CR43_687","first-page":"309","volume-title":"The Traveling Salesman Problem and its Variations","author":"C Rego","year":"2002","unstructured":"Rego C, Glover F (2002) Local Search and\nMetaheuristics. In: Gutin G, Punnen AP (eds) The\nTraveling Salesman Problem and its Variations. Kluwer, Dordrecht, pp\u00a0309\u2013368"},{"key":"687_CR44_687","unstructured":"Rego C, Glover F, Gamboa D, Osterman C: A\u00a0Doubly-Rooted\nStem-and-Cycle Ejection Chain Algorithm for Asymmetric Traveling Salesman\nProblems. submitted"},{"key":"687_CR45_687","doi-asserted-by":"crossref","unstructured":"Trevisan L (1997) When Hamming meets Euclid: the\napproximability of geometric TSP and MST. In: Proc. 29th ACM\nSymp. Theory Comput. ACM, pp 21\u201339","DOI":"10.1145\/258533.258541"},{"key":"687_CR46_687","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1287\/moor.6.3.319","volume":"6","author":"E Zemel","year":"1981","unstructured":"Zemel E (1981) Measuring the quality of approximate solutions\nto zero-one programming problems. Math Oper Res 6:319\u2013332","journal-title":"Math Oper Res"}],"container-title":["Encyclopedia of Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-74759-0_687","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T10:24:57Z","timestamp":1720693497000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-74759-0_687"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387747583","9780387747590"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-74759-0_687","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}