{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T17:50:38Z","timestamp":1785952238010,"version":"3.56.0"},"reference-count":7,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,3,1]],"date-time":"2022-03-01T00:00:00Z","timestamp":1646092800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T00:00:00Z","timestamp":1646265600000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper. Res. Forum"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An O(<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>) heuristic algorithm is described for solving <jats:sc>d<\/jats:sc>-city travelling salesman problems (TSP) whose cost matrix satisfies the triangularity condition. The algorithm involves as substeps the computation of a shortest spanning tree of the graph <jats:italic>G<\/jats:italic> defining the TSP and the finding of a minimum cost perfect matching of a certain induced subgraph of <jats:italic>G<\/jats:italic>. A worst-case analysis of this heuristic shows that the ratio of the answer obtained to the optimum TSP solution is strictly less than 3\/2. This represents a 50% reduction over the value 2 which was the previously best known such ratio for the performance of other polynomial growth algorithms for the TSP.<\/jats:p>","DOI":"10.1007\/s43069-021-00101-z","type":"journal-article","created":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T02:02:57Z","timestamp":1646272977000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":136,"title":["Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem"],"prefix":"10.1007","volume":"3","author":[{"given":"Nicos","family":"Christofides","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,3,3]]},"reference":[{"key":"101_CR1","unstructured":"Christofides N (1975) Graph theory \u2013 an algorithmic approach, Academic Press, London"},{"key":"101_CR2","doi-asserted-by":"crossref","unstructured":"Christofides N (1970) The shortest Hamiltonian chain of a graph. SIAM J Appl Math\u00a019, 689","DOI":"10.1137\/0119070"},{"key":"101_CR3","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1287\/mnsc.17.5.259","volume":"17","author":"S Eilon","year":"1971","unstructured":"Eilon S, Christofides N (1971) The loading problem. Man Sci 17:259","journal-title":"Man Sci"},{"key":"101_CR4","doi-asserted-by":"crossref","unstructured":"Garey MR, Johnson DS (1976) The complexity of near-optimal graph coloring. J ACM","DOI":"10.1145\/321921.321926"},{"key":"101_CR5","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson DS, Demers A, Ullman JD, Garey MR, Grabam RL (1974) Worst-case performance bounds for simple 1-dimensional packing algorithms. SIAM J on Comp 3:299","journal-title":"SIAM J on Comp"},{"key":"101_CR6","unstructured":"Lawler E Combinatorial optimization, (to be published)"},{"key":"101_CR7","doi-asserted-by":"crossref","unstructured":"Rosenkrantz DJ, Stearns RE, Lewis PN (1974) Approximate algorithms for the travelling salesman problem, Proc. 15th\u00a0IEEE Symp Switch Automata Theor 33","DOI":"10.1109\/SWAT.1974.4"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-021-00101-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-021-00101-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-021-00101-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T11:39:17Z","timestamp":1648208357000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-021-00101-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":7,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["101"],"URL":"https:\/\/doi.org\/10.1007\/s43069-021-00101-z","relation":{},"ISSN":["2662-2556"],"issn-type":[{"value":"2662-2556","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3]]},"assertion":[{"value":"4 October 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"20"}}