{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T14:38:58Z","timestamp":1768055938441,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T00:00:00Z","timestamp":1744848000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T00:00:00Z","timestamp":1744848000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE-1650441"],"award-info":[{"award-number":["DGE-1650441"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["PGSD3-532673-2019"],"award-info":[{"award-number":["PGSD3-532673-2019"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["CCF-2007009"],"award-info":[{"award-number":["CCF-2007009"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["CCF-1908517"],"award-info":[{"award-number":["CCF-1908517"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2153331"],"award-info":[{"award-number":["CCF-2153331"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,1]]},"DOI":"10.1007\/s10107-025-02215-2","type":"journal-article","created":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T06:43:23Z","timestamp":1744872203000},"page":"95-143","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The two-stripe symmetric circulant TSP is in P"],"prefix":"10.1007","volume":"215","author":[{"given":"Samuel C.","family":"Gutekunst","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6362-2048","authenticated-orcid":false,"given":"Billy","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,17]]},"reference":[{"key":"2215_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2024.107133","volume":"55","author":"A Beal","year":"2024","unstructured":"Beal, A., Bouabida, Y., Gutekunst, S.C., Rustad, A.: Circulant tsp special cases: easily-solvable cases and improved approximations. Oper. Res. Lett. 55, 107133 (2024)","journal-title":"Oper. Res. Lett."},{"key":"2215_CR2","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for (1, 2)-TSP. In Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithm, pp. 641\u2013648 (2006)","DOI":"10.1145\/1109557.1109627"},{"issue":"1","key":"2215_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0166-218X(91)90024-Q","volume":"32","author":"R Burkard","year":"1991","unstructured":"Burkard, R., Sandholzer, W.: Efficiently solvable special cases of bottleneck travelling salesman problems. Discret. Appl. Math. 32(1), 61\u201376 (1991). https:\/\/doi.org\/10.1016\/0166-218X(91)90024-Q. (http:\/\/www.sciencedirect.com\/science\/article\/pii\/0166218X9190024Q)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"2215_CR4","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF02614311","volume":"79","author":"RE Burkard","year":"1997","unstructured":"Burkard, R.E.: Efficiently solvable special cases of hard combinatorial optimization problems. Math. Program. 79(1), 55\u201369 (1997). https:\/\/doi.org\/10.1007\/BF02614311","journal-title":"Math. Program."},{"issue":"3","key":"2215_CR5","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/S0036144596297514","volume":"40","author":"RE Burkard","year":"1998","unstructured":"Burkard, R.E., De\u012dneko, V.G., van Dal, R., van der Veen, J.A.A., Woeginger, G.J.: Well-solvable special cases of the traveling salesman problem: a survey. SIAM Rev. 40(3), 496\u2013546 (1998). https:\/\/doi.org\/10.1137\/S0036144596297514. (http:\/\/dx.doi.org\/10.1137\/S0036144596297514)","journal-title":"SIAM Rev."},{"issue":"1","key":"2215_CR6","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0024-3795(98)10126-X","volume":"285","author":"B Codenotti","year":"1998","unstructured":"Codenotti, B., Gerace, I., Vigna, S.: Hardness results and spectral techniques for combinatorial problems on circulant graphs. Linear Algebra Appl. 285(1), 123\u2013142 (1998). https:\/\/doi.org\/10.1016\/S0024-3795(98)10126-X. (http:\/\/www.sciencedirect.com\/science\/article\/pii\/S002437959810126X)","journal-title":"Linear Algebra Appl."},{"issue":"5","key":"2215_CR7","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1287\/opre.25.5.741","volume":"25","author":"RS Garfinkel","year":"1977","unstructured":"Garfinkel, R.S.: Minimizing wallpaper waste, part 1: a class of traveling salesman problems. Oper. Res. 25(5), 741\u2013751 (1977). https:\/\/doi.org\/10.1287\/opre.25.5.741","journal-title":"Oper. Res."},{"key":"2215_CR8","unstructured":"Gerace, I., Greco, F.: Bounds for the symmetric circulant traveling salesman problem. Rapporto Tecnico 4\/2006, Dipartimento de Matematica e Informatica, Universit\u00e0 di Perugia (2006)"},{"issue":"1","key":"2215_CR9","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1017\/S0960129508006609","volume":"18","author":"I Gerace","year":"2008","unstructured":"Gerace, I., Greco, F.: The travelling salesman problem in symmetric circulant matrices with two stripes. Math. Struct. Comput. Sci. 18(1), 165\u2013175 (2008)","journal-title":"Math. Struct. Comput. Sci."},{"key":"2215_CR10","first-page":"87","volume-title":"The traveling salesman problem: a guided tour of combinatorial optimization","author":"PC Gilmore","year":"1985","unstructured":"Gilmore, P.C., Lawler, E.L., Shmoys, D.B.: Well-solved special cases. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.) The traveling salesman problem: a guided tour of combinatorial optimization, pp. 87\u2013143. John Wiley and Sons, New York (1985)"},{"key":"2215_CR11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.entcs.2006.07.032","volume":"169","author":"F Greco","year":"2007","unstructured":"Greco, F., Gerace, I.: The traveling salesman problem in circulant weighted graphs with two stripes. Electron. Notes Theoret. Comput. Sci. 169, 99\u2013109 (2007). https:\/\/doi.org\/10.1016\/j.entcs.2006.07.032. (http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1571066107000497)","journal-title":"Electron. Notes Theoret. Comput. Sci."},{"key":"2215_CR12","doi-asserted-by":"crossref","unstructured":"Gutekunst, S.C., Jin, B., Williamson, D.P.: The two-stripe symmetric circulant TSP is in P, (2022). arXiv preprint arXiv:2207.10254","DOI":"10.1007\/978-3-031-06901-7_24"},{"issue":"4","key":"2215_CR13","doi-asserted-by":"publisher","first-page":"2452","DOI":"10.1137\/19M1245840","volume":"33","author":"SC Gutekunst","year":"2019","unstructured":"Gutekunst, S.C., Williamson, D.P.: Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem. SIAM J. Discret. Math. 33(4), 2452\u20132478 (2019)","journal-title":"SIAM J. Discret. Math."},{"key":"2215_CR14","unstructured":"Gutekunst, S.C., Williamson, D.P.: The circlet inequalities: A new, circulant-based facet-defining inequality for the TSP, (2020). arXiv preprint arXiv:2012.12363. To appear in mathematics of operations research"},{"key":"2215_CR15","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780199219858.001.0001","volume-title":"An introduction to the theory of numbers","author":"G Hardy","year":"2008","unstructured":"Hardy, G., Wright, E.: An introduction to the theory of numbers, 6th edn. Oxford University Press, Oxford (2008)","edition":"6"},{"key":"2215_CR16","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/0-306-48213-4_11","volume-title":"Polynomially Solvable Cases of the TSP","author":"SN Kabadi","year":"2007","unstructured":"Kabadi, S.N.: Polynomially Solvable Cases of the TSP, pp. 489\u2013583. Springer US, Boston, MA (2007). https:\/\/doi.org\/10.1007\/0-306-48213-4_11"},{"key":"2215_CR17","first-page":"8","volume":"19","author":"M Karpinski","year":"2012","unstructured":"Karpinski, M., Schmied, R.: On approximation lower bounds for TSP with bounded metrics. Electron. Colloq. Comput. Complex. (ECCC) 19, 8 (2012)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"key":"2215_CR18","volume-title":"The traveling salesman problem: a guided tour of combinatorial optimization","author":"EL Lawler","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The traveling salesman problem: a guided tour of combinatorial optimization. John Wiley and Sons, New Jersey (1985)"},{"key":"2215_CR19","doi-asserted-by":"crossref","unstructured":"Medova, E.: Using QAP bounds for the circulant TSP to design reconfigurable networks. In Quadratic assignment and related problems, proceedings of a DIMACS workshop, New Brunswick, New Jersey, USA, May 20-21, 1993, pp. 275\u2013292 (1993)","DOI":"10.1090\/dimacs\/016\/14"},{"issue":"1","key":"2215_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"2215_CR21","volume-title":"A computational introduction to number theory and algebra","author":"V Shoup","year":"2009","unstructured":"Shoup, V.: A computational introduction to number theory and algebra. Cambridge University Press, Cambridge (2009)"},{"key":"2215_CR22","unstructured":"van der Veen, J.A., van Dal, R., Sieksma, G.: The symmetric circulant traveling salesman problem. Research Memorandum 429, Institute of Economic Research, Faculty of Economics, University of Groningen (1991)"},{"key":"2215_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The design of approximation algorithms. Cambridge University Press, New York (2011)"},{"issue":"1","key":"2215_CR24","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0012-365X(96)00298-1","volume":"176","author":"QF Yang","year":"1997","unstructured":"Yang, Q.F., Burkard, R.E., \u00c7ela, E., Woeginger, G.J.: Hamiltonian cycles in circulant digraphs with two stripes. Discret. Math. 176(1), 233\u2013254 (1997)","journal-title":"Discret. Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02215-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02215-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02215-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T12:21:00Z","timestamp":1768047660000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02215-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,17]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["2215"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02215-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,17]]},"assertion":[{"value":"15 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}},{"value":"The authors have none to declare.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}