{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T01:36:22Z","timestamp":1781487382554,"version":"3.54.1"},"reference-count":28,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8990,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1982,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the asymmetric traveling salesman problem for which the triangular inequality is satisfied. For various heuristics we construct examples to show that the worst\u2010case ratio of length of tour found to minimum length tour is (<jats:italic>n<\/jats:italic>) for <jats:italic>n<\/jats:italic> city problems. We also provide a new <jats:italic>O<\/jats:italic>([log<jats:sub>2<\/jats:sub><jats:italic>n<\/jats:italic>]) heuristic.<\/jats:p>","DOI":"10.1002\/net.3230120103","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T12:56:13Z","timestamp":1178888173000},"page":"23-39","source":"Crossref","is-referenced-by-count":178,"title":["On the worst\u2010case performance of some algorithms for the asymmetric traveling salesman problem"],"prefix":"10.1002","volume":"12","author":[{"given":"A. M.","family":"Frieze","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G.","family":"Galbiati","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F.","family":"Maffioli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","article-title":"Worst\u2010case analysis of a new heuristic for the travelling salesman problem","author":"Christofides N.","journal-title":"Mathematical Programming"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.4.568"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"S. A.Cook The complexity of theorem proving procedures.Proceedings 3rd Annual ACM Symposium on Theory of Computing(1971)151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588956"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"e_1_2_1_7_2","unstructured":"J.Edmonds Optimum Branchings Mathematics of the Decision Sciences Part 1 American Mathematical Society (1968)346\u2013364."},{"key":"e_1_2_1_8_2","unstructured":"M. L.Fisher G. L.Nemhauser andL. A.Wolsey An analysis of approximations for finding a maximum weight hamiltonian circuit. Unpublished."},{"key":"e_1_2_1_9_2","first-page":"93","article-title":"Worst\u2010case analysis of algorithms for travelling salesman problems","volume":"32","author":"Frieze A. M.","year":"1979","journal-title":"Oper. Res. Verfahren"},{"key":"e_1_2_1_10_2","unstructured":"A. M.Frieze A generalisation of the greedy algorithm for independence systems. Unpublished."},{"key":"e_1_2_1_11_2","unstructured":"A. M.Frieze An extension of Christofides' Heuristic to the k\u2010person travelling salesman problem. Submitted to Discrete Appl. Math."},{"key":"e_1_2_1_12_2","volume-title":"Computers and intractability: A guide to the theory of NP\u2010completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_13_2","first-page":"204","article-title":"Evaluating a sequential routing algorithm","volume":"9","author":"Golden B. L.","year":"1977","journal-title":"A.I.I.E. Trans."},{"key":"e_1_2_1_14_2","unstructured":"D.Hausmann T. A.Jenkyns andB.Korte Worst\u2010case analysis of greedy type algorithms for independence systems. Report No. 7781\u2010OR University of Bonn (1977)."},{"key":"e_1_2_1_15_2","unstructured":"T. A.Jenkyns The efficacy of the greedy algorithm. Proceedings 7th S\u2010E Conference on Combinatorics Graph Theory and Computing(1976)341\u2013350."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.10.2.225"},{"key":"e_1_2_1_17_2","first-page":"85","volume-title":"Complexity of Computer Computations","author":"Karp R. M.","year":"1973"},{"key":"e_1_2_1_18_2","first-page":"15","volume-title":"Proceedings 6th South Eastern Conference on Combinatorics, Graph Theory and Computing","author":"Karp R. M.","year":"1975"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70322-4"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1965.tb04146.x"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"e_1_2_1_22_2","first-page":"26","article-title":"On a method of approximating solutions to the travelling salesman problem","volume":"16","author":"Minina T. R.","year":"1975","journal-title":"Sov. Math."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/3.4.362"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.3.434"},{"key":"e_1_2_1_25_2","first-page":"864","article-title":"Discrete Optimizing S.I.A.M.","volume":"13","author":"Reiter S.","year":"1965","journal-title":"J. Appl. Math."},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"D. J.Rosenkrantz R. E.Stearns andP. M.Lewis Approximate algorithms for the travelling salesperson problem.Proceedings of 15th IEEE Symposium on Switching and Automata Theory(1974)33\u201342.","DOI":"10.1109\/SWAT.1974.4"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1978.147"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1971.19"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230120103","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230120103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T15:36:24Z","timestamp":1699803384000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230120103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,3]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1982,3]]}},"alternative-id":["10.1002\/net.3230120103"],"URL":"https:\/\/doi.org\/10.1002\/net.3230120103","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,3]]}}}