{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:43Z","timestamp":1750307203138,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,4,1]],"date-time":"2012-04-01T00:00:00Z","timestamp":1333238400000},"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":[[2012,4]]},"abstract":"<jats:p>We present approximation algorithms for almost all variants of the multicriteria traveling salesman problem (TSP).<\/jats:p>\n          <jats:p>\n            First, we devise randomized approximation algorithms for multicriteria maximum traveling salesman problems (Max-TSP). For multicriteria Max-STSP where the edge weights have to be symmetric, we devise an algorithm with an approximation ratio of 2\/3 - \u03b5. For multicriteria Max-ATSP where the edge weights may be asymmetric, we present an algorithm with a ratio of 1\/2 - \u03b5. Our algorithms work for any fixed number\n            <jats:italic>k<\/jats:italic>\n            of objectives. Furthermore, we present a deterministic algorithm for bicriteria Max-STSP that achieves an approximation ratio of 7\/27.\n          <\/jats:p>\n          <jats:p>\n            Finally, we present a randomized approximation algorithm for the asymmetric multicriteria minimum TSP with triangle inequality (Min-ATSP). This algorithm achieves a ratio of log\n            <jats:italic>n<\/jats:italic>\n            + \u03b5.\n          <\/jats:p>","DOI":"10.1145\/2151171.2151180","type":"journal-article","created":{"date-parts":[[2012,4,24]],"date-time":"2012-04-24T18:41:10Z","timestamp":1335292870000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["On approximating multicriteria TSP"],"prefix":"10.1145","volume":"8","author":[{"given":"Bodo","family":"Manthey","sequence":"first","affiliation":[{"name":"University of Twente, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,4,25]]},"reference":[{"volume-title":"Network Flows: Theory, Algorithms, and Applications","year":"1993","author":"Ahuja R. K.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00376-1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11537311_29"},{"volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Asadpour A.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1131-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_16"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.07.004"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2000.tb00182.x"},{"key":"e_1_2_1_9_1","unstructured":"Ehrgott M. 2005. Multicriteria Optimization. Springer Berlin.   Ehrgott M. 2005. Multicriteria Optimization. Springer Berlin."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002910000046"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120103"},{"key":"e_1_2_1_13_1","unstructured":"Gilmore P. C. Lawler E. L. and Shmoys D. B. 1985. Well-solved special cases. In The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization E. L. Lawler et al. Eds. Wiley 87--143.  Gilmore P. C. Lawler E. L. and Shmoys D. B. 1985. Well-solved special cases. In The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization E. L. Lawler et al. Eds. Wiley 87--143."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082041"},{"volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS). 637--648","year":"2009","author":"Manthey B.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9011-z"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_23"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796569"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Ravi R.\n     and \n      \n      \n      Goemans M. X\n      \n  \n  . \n  1996\n  . The constrained minimum spanning tree problem. In Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT) R. G. Karlsson and A. Lingas Eds. Lecture Notes in Computer Science vol. \n  1097 Springer Berlin 66--75.   Ravi R. and Goemans M. X. 1996. The constrained minimum spanning tree problem. In Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT) R. G. Karlsson and A. Lingas Eds. Lecture Notes in Computer Science vol. 1097 Springer Berlin 66--75.","DOI":"10.1007\/3-540-61422-2_121"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2151171.2151180","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2151171.2151180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:19Z","timestamp":1750241179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2151171.2151180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.1145\/2151171.2151180"],"URL":"https:\/\/doi.org\/10.1145\/2151171.2151180","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,4]]},"assertion":[{"value":"2009-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}