{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:15:58Z","timestamp":1781345758398,"version":"3.54.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,12,9]],"date-time":"2019-12-09T00:00:00Z","timestamp":1575849600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,9]],"date-time":"2019-12-09T00:00:00Z","timestamp":1575849600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Sciences and Research Council of Canada"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,3]]},"DOI":"10.1007\/s10107-019-01455-3","type":"journal-article","created":{"date-parts":[[2019,12,9]],"date-time":"2019-12-09T13:02:58Z","timestamp":1575896578000},"page":"289-307","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The salesman\u2019s improved tours for fundamental classes"],"prefix":"10.1007","volume":"186","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7884-0219","authenticated-orcid":false,"given":"Sylvia","family":"Boyd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e1s","family":"Seb\u0151","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,12,9]]},"reference":[{"issue":"4","key":"1455_CR1","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1287\/moor.1080.0337","volume":"33","author":"G Benoit","year":"2008","unstructured":"Benoit, G., Boyd, S.: Finding the exact integrality gap for small traveling salesman problems. Math. Oper. Res. 33(4), 921\u2013931 (2008)","journal-title":"Math. Oper. Res."},{"key":"1455_CR2","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF02604639","volume":"38","author":"A Bouchet","year":"1987","unstructured":"Bouchet, A.: Greedy algorithm and symmetric matroids. Math. Program. 38, 147\u2013159 (1987)","journal-title":"Math. Program."},{"issue":"1","key":"1455_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1137\/S0895480191222926","volume":"8","author":"A Bouchet","year":"1995","unstructured":"Bouchet, A., Cunningham, W.: Delta-matroids, jump systems, and bisubmodular polyhedra. SIAM J. Discrete Math. 8(1), 17\u201332 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"1455_CR4","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.disopt.2011.05.002","volume":"8","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Carr, R.: Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optim. 8, 525\u2013539 (2011)","journal-title":"Discrete Optim."},{"issue":"2","key":"1455_CR5","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1137\/110843514","volume":"27","author":"S Boyd","year":"2013","unstructured":"Boyd, S., Iwata, S., Takazawa, K.: Finding 2-factors closer to TSP tours in cubic graphs. SIAM J. Discrete Math. 27(2), 918\u2013939 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"1455_CR6","doi-asserted-by":"publisher","first-page":"259","DOI":"10.7151\/dmgt.1053","volume":"17","author":"H Broersma","year":"1997","unstructured":"Broersma, H., Li, X.: Spanning trees with many or few colors in edge-colored graphs. Discuss. Math. Graph Theory 17, 259\u2013269 (1997)","journal-title":"Discuss. Math. Graph Theory"},{"key":"1455_CR7","doi-asserted-by":"crossref","unstructured":"Carr, R., Ravi, R.: A new bound for the 2-edge connected subgraph problem. In: Proceedings of the Integer Programming and Combinatorial Optimizaiton (IPCO). Lecture Notes in Computer Science, pp. 112\u2013125. Springer (1998)","DOI":"10.1007\/3-540-69346-7_9"},{"key":"1455_CR8","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s10107-004-0506-y","volume":"100","author":"R Carr","year":"2004","unstructured":"Carr, R., Vempala, S.: On the Held\u2013Karp relaxation for the asymmetric and symmetric travelling salesman problem. Math. Program. A 100, 569\u2013587 (2004)","journal-title":"Math. Program. A"},{"key":"1455_CR9","unstructured":"Christofides, N.: Worst Case Analysis of a New Heuristic for the Traveling Salesman Problem. Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh (1976)"},{"key":"1455_CR10","unstructured":"Cunningham, W.H.: On Bounds for the Metric TSP, Manuscript. School of Mathematics and Statistics, Carleton University, Ottawa (1986)"},{"key":"1455_CR11","unstructured":"Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Sch\u00f6nheim, J. (eds.) Combinatorial Structures and Their Applications. Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications 1969. Gordon and Breach, New York (1970)"},{"issue":"1","key":"1455_CR12","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5(1), 88\u2013124 (1973)","journal-title":"Math. Program."},{"key":"1455_CR13","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 550\u2013559 (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"1455_CR14","first-page":"335","volume":"69","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69, 335\u2013349 (1995)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1455_CR15","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\u2013t-tours by Gao trees. Math. Program. 172(1\u20132), 191\u2013207 (2018)","journal-title":"Math. Program."},{"key":"1455_CR16","volume-title":"The Traveling Salesman Problem\u2014A Guided Tour of Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1985","unstructured":"Gr\u00f6tschel, M., Padberg, M.W.: Polyhedral theory. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem\u2014A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)"},{"key":"1455_CR17","unstructured":"Haddadan, A., Newman, A., Ravi, R.: Shorter Tours and Longer Detours: Uniform Covers and a Bit Beyond. arXiv:1707.05387v3 [cs.DS] (2017)"},{"issue":"3","key":"1455_CR18","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1137\/070683635","volume":"22","author":"T Kaiser","year":"2008","unstructured":"Kaiser, T., \u0160krekovski, R.: Cycles intersecting edge-cuts of prescribed sizes. SIAM J. Discrete Math. 22(3), 861\u2013874 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"1455_CR19","unstructured":"Kotzig, A.: Moves without forbidden transitions in a graph. Mat. Casopis Sloven, Akad. Vied 18, 76\u201380 (1968)"},{"issue":"2","key":"1455_CR20","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1287\/moor.2013.0608","volume":"39","author":"F Schalekamp","year":"2014","unstructured":"Schalekamp, F., Williamson, D., van Zuylen, A.: 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd\u2013Carr conjecture. Math. Oper. Res. 39(2), 403\u2013417 (2014)","journal-title":"Math. Oper. Res."},{"key":"1455_CR21","volume-title":"Combinatorial Optimization","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)"},{"key":"1455_CR22","doi-asserted-by":"publisher","unstructured":"Seb\u0151, A., Benchetrit, Y., Stehlik, M.: Problems About Uniform Covers, with Tours and Detours. Report No.\u00a051\/2014, pp. 2912\u20132915. Matematisches Forschungsinstitut Oberwolfach (2015). https:\/\/doi.org\/10.4171\/OWR\/2014\/51","DOI":"10.4171\/OWR\/2014\/51"},{"key":"1455_CR23","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","volume":"34","author":"A Seb\u0151","year":"2014","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nice ears. Combinatorica 34, 597\u2013629 (2014)","journal-title":"Combinatorica"},{"key":"1455_CR24","doi-asserted-by":"crossref","unstructured":"Seb\u0151, A., van Zuylen, A.: The salesman\u2019s improved paths: a 3\/2+1\/34 approximation. In: Foundations of Computer Science (FOCS), pp. 118\u2013127 (2016)","DOI":"10.1109\/FOCS.2016.21"},{"key":"1455_CR25","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"D Shmoys","year":"1990","unstructured":"Shmoys, D., Williamson, D.: Analysis of the Held\u2013Karp TSP bound: a monotoncity property with application. Inf. Process. Lett. 35, 281\u2013285 (1990)","journal-title":"Inf. Process. Lett."},{"key":"1455_CR26","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"L Wolsey","year":"1980","unstructured":"Wolsey, L.: Heuristic analysis, linear programming and branch and bound. Math. Program. Study 13, 121\u2013134 (1980)","journal-title":"Math. Program. Study"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01455-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01455-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01455-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T09:48:22Z","timestamp":1613036902000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01455-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,9]]},"references-count":26,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["1455"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01455-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,9]]},"assertion":[{"value":"29 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 November 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}