{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:30Z","timestamp":1740122430348,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,6,2]],"date-time":"2020-06-02T00:00:00Z","timestamp":1591056000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,2]],"date-time":"2020-06-02T00:00:00Z","timestamp":1591056000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","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":[[2020,8]]},"DOI":"10.1007\/s10878-020-00588-y","type":"journal-article","created":{"date-parts":[[2020,6,2]],"date-time":"2020-06-02T12:04:34Z","timestamp":1591099474000},"page":"303-332","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A class of exponential neighbourhoods for the quadratic travelling salesman problem"],"prefix":"10.1007","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5737-5821","authenticated-orcid":false,"given":"Brad D.","family":"Woods","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abraham P.","family":"Punnen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,2]]},"reference":[{"key":"588_CR1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","volume":"123","author":"R Ahuja","year":"2002","unstructured":"Ahuja R, Ergun \u00d6, Orlin J, Punnen A (2002) A survey of very large-scale neighborhood search techniques. Discrete Appl Math 123:75\u2013102","journal-title":"Discrete Appl Math"},{"key":"588_CR2","volume-title":"The traveling salesman problem: a computational study","author":"D Applegate","year":"2011","unstructured":"Applegate D, Bixby R, Chvatal V, Cook W (2011) The traveling salesman problem: a computational study. Princeton University Press, Princeton"},{"key":"588_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.disopt.2005.10.001","volume":"3","author":"E Balas","year":"2006","unstructured":"Balas E, Carr R, Fischetti M, Simonetti N (2006) New facets of the STS polytope generated from known facets of the ATS polytope. Discrete Optim 3:3\u201319","journal-title":"Discrete Optim"},{"key":"588_CR4","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1287\/ijoc.4.4.387","volume":"4","author":"J Bentley","year":"1992","unstructured":"Bentley J (1992) Fast algorithms for geometric traveling salesman problems. ORSA J Comput 4:387\u2013411","journal-title":"ORSA J Comput"},{"key":"588_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph theory with applications","author":"J Bondy","year":"1976","unstructured":"Bondy J, Murty U et al (1976) Graph theory with applications. Macmillan, London"},{"key":"588_CR6","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1287\/moor.24.1.262","volume":"24","author":"R Burkard","year":"1999","unstructured":"Burkard R, Deineko V, Woeginger G (1999) Erratum: the travelling salesman and the PQ-tree. Math Oper Res 24:262\u2013272","journal-title":"Math Oper Res"},{"key":"588_CR7","volume-title":"In pursuit of the traveling salesman: mathematics at the limits of computation","author":"W Cook","year":"2012","unstructured":"Cook W (2012) In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press, Princeton"},{"key":"588_CR8","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF02591867","volume":"26","author":"G Cornu\u00e9jols","year":"1983","unstructured":"Cornu\u00e9jols G, Naddef D, Pulleyblank W (1983) Halin graphs and the travelling salesman problem. Math Program 26:287\u2013294","journal-title":"Math Program"},{"key":"588_CR9","first-page":"159","volume":"87","author":"V De\u012dneko","year":"2000","unstructured":"De\u012dneko V, Woeginger G (2000) A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Math Program 87:159\u2013542","journal-title":"Math Program"},{"key":"588_CR10","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0377-2217(87)90165-2","volume":"28","author":"K Dudzi\u0144ski","year":"1987","unstructured":"Dudzi\u0144ski K, Walukiewicz S (1987) Exact methods for the knapsack problem and its generalizations. Eur J Oper Res 28:3\u201321","journal-title":"Eur J Oper Res"},{"key":"588_CR11","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/j.disopt.2005.10.002","volume":"3","author":"\u00d6 Ergun","year":"2006","unstructured":"Ergun \u00d6, Orlin J (2006) A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem. Discrete Optim 3:78\u201385 The Traveling Salesman Problem","journal-title":"Discrete Optim"},{"key":"588_CR12","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1137\/110858665","volume":"28","author":"A Fischer","year":"2014","unstructured":"Fischer A (2014) An analysis of the asymmetric quadratic traveling salesman polytope. SIAM J Discrete Math 28:240\u2013276","journal-title":"SIAM J Discrete Math"},{"key":"588_CR13","doi-asserted-by":"crossref","unstructured":"Fischer A (2016) A polyhedral study of the quadratic traveling salesman problem. In: Operations research proceedings 2014, Springer, pp 143\u2013149","DOI":"10.1007\/978-3-319-28697-6_21"},{"key":"588_CR14","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s10107-012-0568-1","volume":"142","author":"A Fischer","year":"2013","unstructured":"Fischer A, Helmberg C (2013) The symmetric quadratic traveling salesman problem. Math Program 142:205\u2013254","journal-title":"Math Program"},{"key":"588_CR15","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.dam.2013.09.011","volume":"166","author":"A Fischer","year":"2014","unstructured":"Fischer A, Fischer F, J\u00e4ger G, Keilwagen J, Molitor P, Grosse I (2014) Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics. Discrete Appl Math 166:97\u2013114","journal-title":"Discrete Appl Math"},{"key":"588_CR16","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Co., San Francisco"},{"key":"588_CR17","first-page":"87","volume-title":"The traveling salesman problem: a guided tour of combinatorial optimization","author":"P Gilmore","year":"1986","unstructured":"Gilmore P, Lawler E, Shmoys D (1986) In: Lawler EL, Lenstra JK, Rinnooy Kan HG (eds) The traveling salesman problem: a guided tour of combinatorial optimization. Wiley, Hoboken, pp 87\u2013143"},{"key":"588_CR18","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1057\/palgrave.jors.2600392","volume":"48","author":"F Glover","year":"1997","unstructured":"Glover F, Punnen A (1997) The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms. J Oper Res Soc 48:502\u2013510","journal-title":"J Oper Res Soc"},{"key":"588_CR19","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1002\/net.21801","volume":"71","author":"F Glover","year":"2018","unstructured":"Glover F, Rego C (2018) New assignment-based neighborhoods for traveling salesman and routing problems. Networks 71:171\u2013187","journal-title":"Networks"},{"key":"588_CR20","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.orl.2013.01.004","volume":"41","author":"V Goyal","year":"2013","unstructured":"Goyal V, Ravi R (2013) An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set. Oper Res Lett 41:191\u2013196","journal-title":"Oper Res Lett"},{"key":"588_CR21","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/s10107-009-0287-4","volume":"126","author":"V Goyal","year":"2011","unstructured":"Goyal V, Genc-Kaya L, Ravi R (2011) An FPTAS for minimizing the product of two non-negative linear cost functions. Math Program 126:401\u2013405","journal-title":"Math Program"},{"key":"588_CR22","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0305-0548(98)00064-1","volume":"26","author":"G Gutin","year":"1999","unstructured":"Gutin G (1999) Exponential neighbourhood local search for the traveling salesman problem. Comput Oper Res 26:313\u2013320","journal-title":"Comput Oper Res"},{"key":"588_CR23","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/s10732-005-3487-y","volume":"11","author":"G Gutin","year":"2005","unstructured":"Gutin G, Glover F (2005) Further extension of the TSP assign neighborhood. J Heuristics 11:501\u2013505","journal-title":"J Heuristics"},{"key":"588_CR24","series-title":"Combinatorial optimization","volume-title":"The traveling salesman problem and its variations","year":"2002","unstructured":"Gutin G, Punnen A (eds) (2002) The traveling salesman problem and its variations, vol 12. Combinatorial optimization. Springer, New York"},{"key":"588_CR25","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/S0305-0548(98)00065-3","volume":"26","author":"G Gutin","year":"1999","unstructured":"Gutin G, Yeo A (1999) Small diameter neighbourhood graphs for the traveling salesman problem: at most four moves from tour to tour. Comput Oper Res 26:321\u2013327","journal-title":"Comput Oper Res"},{"key":"588_CR26","unstructured":"H\u00e5stad J (1996) Clique is hard to approximate within $$n ^{1-\\epsilon }$$. In: Proceedings of 37th annual symposium on foundations of computer science, 1996, IEEE, pp 627\u2013636"},{"key":"588_CR27","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1007\/s10878-017-0219-9","volume":"35","author":"H Hu","year":"2018","unstructured":"Hu H, Sotirov R (2018) Special cases of the quadratic shortest path problem. J Comb Optim 35:754\u2013777","journal-title":"J Comb Optim"},{"key":"588_CR28","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-540-85097-7_20","volume-title":"Combinatorial optimization and applications","author":"G J\u00e4ger","year":"2008","unstructured":"J\u00e4ger G, Molitor P (2008) Algorithms and experimental study for the traveling salesman problem of second order. In: Yang B, Du D-Z, Wang C (eds) Combinatorial optimization and applications, vol 5165. Lecture notes in computer science. Springer, Berlin, pp 211\u2013224"},{"key":"588_CR29","first-page":"85","volume-title":"Reducibility among combinatorial problems","author":"R Karp","year":"1972","unstructured":"Karp R (1972) Reducibility among combinatorial problems. Springer, Boston, pp 85\u2013103"},{"key":"588_CR30","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Introduction to NP-completeness of knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U, Pisinger D (2004) Introduction to NP-completeness of knapsack problems. Springer, Berlin"},{"key":"588_CR31","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/s10107-006-0047-7","volume":"110","author":"W Kern","year":"2007","unstructured":"Kern W, Woeginger G (2007) Quadratic programming and combinatorial minimum weight product problems. Math Program 110:641\u2013649","journal-title":"Math Program"},{"key":"588_CR32","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.cor.2013.08.005","volume":"43","author":"J LaRusic","year":"2014","unstructured":"LaRusic J, Punnen A (2014) The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis. Comput Oper Res 43:20\u201335","journal-title":"Comput Oper Res"},{"key":"588_CR33","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/s10732-012-9194-6","volume":"18","author":"J LaRusic","year":"2012","unstructured":"LaRusic J, Punnen A, Aubanel E (2012) Experimental analysis of heuristics for the bottleneck traveling salesman problem. J Heuristics 18:473\u2013503","journal-title":"J Heuristics"},{"key":"588_CR34","volume-title":"The traveling salesman problem: a guided tour of combinatorial optimization","author":"E Lawler","year":"1985","unstructured":"Lawler E, Lenstra J, Kan A, Shmoys D (1985) The traveling salesman problem: a guided tour of combinatorial optimization, vol 3. Wiley, New York"},{"key":"588_CR35","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1287\/opre.1120.1093","volume":"61","author":"S Mittal","year":"2013","unstructured":"Mittal S, Schulz A (2013) A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one. Oper Res 61:386\u2013397","journal-title":"Oper Res"},{"key":"588_CR36","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"N Mladenovi\u0107","year":"1997","unstructured":"Mladenovi\u0107 N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24:1097\u20131100","journal-title":"Comput Oper Res"},{"key":"588_CR37","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1137\/S0097539703431007","volume":"33","author":"J Orlin","year":"2004","unstructured":"Orlin J, Punnen A, Schulz A (2004) Approximate local search in combinatorial optimization. SIAM J Comput 33:1201\u20131214","journal-title":"SIAM J Comput"},{"key":"588_CR38","first-page":"205","volume":"7","author":"AP Punnen","year":"2001","unstructured":"Punnen AP (2001a) Combinatorial optimization with multiplicative objective function. Int J Oper Quant Manag 7:205\u2013210","journal-title":"Int J Oper Quant Manag"},{"key":"588_CR39","first-page":"191","volume":"22","author":"AP Punnen","year":"2001","unstructured":"Punnen AP (2001b) The traveling salesman problem: new polynomial approximation algorithms and domination analysis. J Inf Optim Sci 22:191\u2013206","journal-title":"J Inf Optim Sci"},{"key":"588_CR40","unstructured":"Punnen AP (2018) Approximate local search for combinatorial optimization problems with special non-linear objective functions. Working paper, Department of Mathematics, Simon Fraser University"},{"key":"588_CR41","unstructured":"Punnen AP, Walter M, Woods BD (2018) A characterization of linearizable instances of the quadratic traveling salesman problem. arXiv:1708.07217v3 [cs.DM]"},{"key":"588_CR42","volume-title":"The traveling salesman: computational solutions for TSP applications","author":"G Reinelt","year":"1994","unstructured":"Reinelt G (1994) The traveling salesman: computational solutions for TSP applications. Springer, Berlin"},{"key":"588_CR43","doi-asserted-by":"crossref","unstructured":"Rostami B, Malucelli F, Frey D, Buchheim C (2015) On the quadratic shortest path problem. In: International symposium on experimental algorithms, Springer, pp 379\u2013390","DOI":"10.1007\/978-3-319-20086-6_29"},{"key":"588_CR44","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1016\/j.ejor.2016.03.031","volume":"253","author":"B Rostami","year":"2016","unstructured":"Rostami B, Malucelli F, Belotti P, Gualandi S (2016) Lower bounding procedure for the asymmetric quadratic traveling salesman problem. Eur J Oper Res 253:584\u2013592","journal-title":"Eur J Oper Res"},{"key":"588_CR45","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/j.ejor.2018.01.054","volume":"268","author":"B Rostami","year":"2018","unstructured":"Rostami B, Chassein A, Hopf M, Frey D, Buchheim C, Malucelli F, Goerigk M (2018) The quadratic shortest path problem: complexity, approximability, and solution methods. Eur J Oper Res 268:473\u2013485","journal-title":"Eur J Oper Res"},{"key":"588_CR46","first-page":"91","volume":"6","author":"L Turner","year":"2012","unstructured":"Turner L (2012) Variants of shortest path problems. Algorithmic Oper Res 6:91\u2013104","journal-title":"Algorithmic Oper Res"},{"key":"588_CR47","volume-title":"Integer and combinatorial optimization","author":"L Wolsey","year":"1988","unstructured":"Wolsey L, Nemhauser G (1988) Integer and combinatorial optimization, vol 55. Wiley, Hoboken"},{"key":"588_CR48","unstructured":"Woods B (2010) Generalized travelling salesman problems on Halin graphs. MSc thesis, Science: Department of Mathematics"},{"key":"588_CR49","unstructured":"Woods B, Punnen A (2018a) The quadratic travelling salesman problem over pyramidal tours. Working paper, Department of Mathematics, Simon Fraser University"},{"key":"588_CR50","unstructured":"Woods B, Punnen A (2018b) The quadratic travelling salesman problem on Halin graphs. Working paper, Department of Mathematics, Simon Fraser University"},{"key":"588_CR51","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.disopt.2017.08.005","volume":"26","author":"B Woods","year":"2017","unstructured":"Woods B, Punnen A, Stephen T (2017) A linear time algorithm for the 3-neighbour travelling salesman problem on Halin graphs and extensions. Discrete Optim 26:163\u2013182","journal-title":"Discrete Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00588-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00588-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00588-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T00:35:38Z","timestamp":1622594138000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00588-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,2]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["588"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00588-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,6,2]]},"assertion":[{"value":"2 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}