{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T00:58:41Z","timestamp":1769302721266,"version":"3.49.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,9,15]],"date-time":"2007-09-15T00:00:00Z","timestamp":1189814400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,1]]},"DOI":"10.1007\/s00453-007-9011-z","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T12:07:44Z","timestamp":1189771664000},"page":"69-88","source":"Crossref","is-referenced-by-count":13,"title":["Approximation Algorithms for Multi-Criteria Traveling Salesman Problems"],"prefix":"10.1007","volume":"53","author":[{"given":"Bodo","family":"Manthey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L.","family":"Shankar Ram","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,9,15]]},"reference":[{"issue":"1\u20133","key":"9011_CR1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0304-3975(03)00376-1","volume":"310","author":"E. Angel","year":"2004","unstructured":"Angel, E., Bampis, E., Gourv\u00e9s, L.: Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem. Theor. Comput. Sci. 310(1\u20133), 135\u2013146 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9011_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/11537311_29","volume-title":"Proc. of the 15th Int. Symp. on Fundamentals of Computation Theory (FCT)","author":"E. Angel","year":"2005","unstructured":"Angel, E., Bampis, E., Gourv\u00e9s, L., Monnot, J.: (Non-)approximability for the multi-criteria TSP(1,2). In: Li\u015bkiewicz, M., Reischuk, R. (eds.) Proc. of the 15th Int. Symp. on Fundamentals of Computation Theory (FCT). Lecture Notes in Computer Science, vol. 3623, pp. 329\u2013340. Springer, New York (2005)"},{"key":"9011_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, New York (1999)"},{"issue":"2","key":"9011_CR4","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0166-218X(87)90067-9","volume":"16","author":"F. Barahona","year":"1987","unstructured":"Barahona, F., Pulleyblank, W.R.: Exact arborescences, matchings and cycles. Discret. Appl. Math. 16(2), 91\u201399 (1987)","journal-title":"Discret. Appl. Math."},{"key":"9011_CR5","first-page":"641","volume-title":"Proc. of the 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"P. Berman","year":"2006","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for (1,2)-TSP. In: Proc. of the 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 641\u2013648. SIAM, Philadelphia (2006)"},{"key":"9011_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/978-3-540-27821-4_6","volume-title":"Proc. of the 7th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"M. Bl\u00e4ser","year":"2004","unstructured":"Bl\u00e4ser, M.: A 3\/4-approximation algorithm for maximum ATSP with weights zero and one. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) Proc. of the 7th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Lecture Notes in Computer Science, vol. 3122, pp. 61\u201371. Springer, New York (2004)"},{"issue":"4","key":"9011_CR7","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1016\/j.jda.2005.07.004","volume":"4","author":"M. Bl\u00e4ser","year":"2006","unstructured":"Bl\u00e4ser, M., Manthey, B., Sgall, J.: An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discret. Algorithms 4(4), 623\u2013632 (2006)","journal-title":"J. Discret. Algorithms"},{"issue":"3","key":"9011_CR8","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0020-0190(00)00089-2","volume":"75","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Approximation algorithms for the TSP with sharpened triangle inequality. Inf. Process. Lett. 75(3), 133\u2013138 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"1-3","key":"9011_CR9","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.tcs.2006.10.026","volume":"370","author":"L.S. Chandran","year":"2007","unstructured":"Chandran, L.S., Ram, L.S.: On the relationship between ATSP and the cycle cover problem. Theor. Comput. Sci. 370(1-3), 218\u2013228 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9011_CR10","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report\u00a0388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA (1976)"},{"issue":"1","key":"9011_CR11","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1111\/j.1475-3995.2000.tb00182.x","volume":"7","author":"M. Ehrgott","year":"2000","unstructured":"Ehrgott, M.: Approximation algorithms for combinatorial multicriteria optimization problems. Int. Trans. Oper. Res. 7(1), 5\u201331 (2000)","journal-title":"Int. Trans. Oper. Res."},{"key":"9011_CR12","volume-title":"Multicriteria Optimization","author":"M. Ehrgott","year":"2005","unstructured":"Ehrgott, M.: Multicriteria Optimization. Springer, New York (2005)"},{"issue":"4","key":"9011_CR13","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s002910000046","volume":"22","author":"M. Ehrgott","year":"2000","unstructured":"Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectrum 22(4), 425\u2013460 (2000)","journal-title":"OR Spectrum"},{"key":"9011_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"9011_CR15","first-page":"87","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"P.C. Gilmore","year":"1985","unstructured":"Gilmore, P.C., Lawler, E.L., Shmoys, D.B.: Well-solved special cases. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, pp. 87\u2013143. Wiley, New York (1985)"},{"key":"9011_CR16","volume-title":"The Traveling Salesman Problem and its Variations","year":"2002","unstructured":"Gutin, G., Punnen, A.P. (eds.): The Traveling Salesman Problem and its Variations. Kluwer Academic, Dordrecht (2002)"},{"issue":"4","key":"9011_CR17","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H. Kaplan","year":"2005","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.I.: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM 52(4), 602\u2013626 (2005)","journal-title":"J. ACM"},{"key":"9011_CR18","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.): The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York (1985)"},{"key":"9011_CR19","series-title":"North-Holland Mathematics Studies","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. North-Holland Mathematics Studies, vol. 121. Elsevier, Amsterdam (1986)"},{"issue":"1","key":"9011_CR20","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"issue":"2","key":"9011_CR21","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H.: The complexity of restricted spanning tree problems. J. ACM 29(2), 285\u2013309 (1982)","journal-title":"J. ACM"},{"key":"9011_CR22","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proc. of the 41st Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp.\u00a086\u201392. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892068"},{"issue":"3","key":"9011_CR23","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D.J. Rosenkrantz","year":"1977","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3), 563\u2013581 (1977)","journal-title":"SIAM J. Comput."},{"key":"9011_CR24","doi-asserted-by":"crossref","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"W.T. Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347\u2013352 (1954)","journal-title":"Can. J. Math."},{"key":"9011_CR25","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9011-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9011-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9011-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:44:59Z","timestamp":1559123099000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9011-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,15]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["9011"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9011-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,15]]}}}