{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T18:10:34Z","timestamp":1791396634679,"version":"4.3.3"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>\n            We present a polynomial time factor 0.999 \u010b log\n            <jats:italic>n<\/jats:italic>\n            approximation algorithm for the asymmetric traveling salesperson problem with triangle inequality.\n          <\/jats:p>","DOI":"10.1145\/1383369.1383378","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T11:56:36Z","timestamp":1219838196000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["A new approximation algorithm for the asymmetric TSP with triangle inequality"],"prefix":"10.1145","volume":"4","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[{"name":"Saarland University, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,8,22]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"Ahuja , R. K. , Magnanti , T. L. , and Orlin , J. B . 1993 . Network Flows: Theory, Algorithms, and Applications . Prentice Hall . Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 17th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA). 641--648","author":"Berman P.","unstructured":"Berman , P. , and Karpinski , M . 2006. 8\/7-approximation algorithm for (1, 2)-TSP . In Proceedings of the 17th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA). 641--648 . Berman, P., and Karpinski, M. 2006. 8\/7-approximation algorithm for (1, 2)-TSP. In Proceedings of the 17th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA). 641--648."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1131-0"},{"key":"e_1_2_1_5_1","unstructured":"Bl\u00e4ser M. Manthey B. and Sgall J. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discrete Algor. To appear.  Bl\u00e4ser M. Manthey B. and Sgall J. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discrete Algor. To appear."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646514.695821"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646516.696153"},{"key":"e_1_2_1_8_1","volume-title":"Algorithms and Complexity: New Directions and Recent Results","author":"Christofides N.","unstructured":"Christofides , N. 1976. Worst-case analysis of a new heuristic for the travelling salesman problem . In Algorithms and Complexity: New Directions and Recent Results , J. F. Traub, Ed. Academic Press , 441. Christofides, N. 1976. Worst-case analysis of a new heuristic for the travelling salesman problem. In Algorithms and Complexity: New Directions and Recent Results, J. F. Traub, Ed. Academic Press, 441."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120103"},{"key":"e_1_2_1_11_1","volume-title":"Eds","author":"Graham R. L.","year":"1995","unstructured":"Graham , R. L. , Gr\u00f6tschel , M. , and Lov\u00e1sz , L. , Eds . 1995 . Handbook of Combinatorics. Vol. I . Elvsevier . Graham, R. L., Gr\u00f6tschel, M., and Lov\u00e1sz, L., Eds. 1995. Handbook of Combinatorics. Vol. I. Elvsevier."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_13_1","volume-title":"Eds. Combinatorial Optimization","volume":"12","author":"Johnson D. S.","unstructured":"Johnson , D. S. , Gutin , G. , McGeoch , L. A. , Yeo , A. , Zhang , W. , and Zverovitch , A . 2002. Experimental analysis of heuristics for the ATSP. In The Traveling Salesman Problem and Its Variations, G. Gutin and A. P. Punnen , Eds. Combinatorial Optimization , vol. 12 . Kluwer. Johnson, D. S., Gutin, G., McGeoch, L. A., Yeo, A., Zhang, W., and Zverovitch, A. 2002. Experimental analysis of heuristics for the ATSP. In The Traveling Salesman Problem and Its Variations, G. Gutin and A. P. Punnen, Eds. Combinatorial Optimization, vol. 12. Kluwer."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082041"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90011-0"},{"key":"e_1_2_1_16_1","volume-title":"Eds","author":"Lawler E. L.","year":"1985","unstructured":"Lawler , E. L. , Lenstra , J. K. , Kan , A. H. G. R. , and Shmoys , D. B. , Eds . 1985 . The Traveling Salesman Problem. Wiley . Lawler, E. L., Lenstra, J. K., Kan, A. H. G. R., and Shmoys, D. B., Eds. 1985. The Traveling Salesman Problem. Wiley."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102402861"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/31027"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2781820.2781821"},{"key":"e_1_2_1_20_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2001. Approximation Algorithms . Springer . Vazirani, V. V. 2001. Approximation Algorithms. Springer."},{"key":"e_1_2_1_21_1","volume-title":"Lecture notes on approximation algorithms. Tech. rep. RC 21409","author":"Williamson D. P.","unstructured":"Williamson , D. P. 1999. Lecture notes on approximation algorithms. Tech. rep. RC 21409 , IBM T. J. Watson Research Center . Williamson, D. P. 1999. Lecture notes on approximation algorithms. Tech. rep. RC 21409, IBM T. J. Watson Research Center."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383378","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1383369.1383378","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:46Z","timestamp":1750255066000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383378"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1383369.1383378"],"URL":"https:\/\/doi.org\/10.1145\/1383369.1383378","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2004-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}