{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:35:32Z","timestamp":1725478532507},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540695134"},{"type":"electronic","value":"9783540695141"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/11970125_24","type":"book-chapter","created":{"date-parts":[[2007,1,24]],"date-time":"2007-01-24T00:47:40Z","timestamp":1169599660000},"page":"302-315","source":"Crossref","is-referenced-by-count":3,"title":["Approximation Algorithms for Multi-criteria Traveling Salesman Problems"],"prefix":"10.1007","author":[{"given":"Bodo","family":"Manthey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L. Shankar","family":"Ram","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1\u20133","key":"24_CR1","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0310(1\u20133), 135\u2013146 (2004)","journal-title":"Theoretical Computer Science"},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/11537311_29","volume-title":"Fundamentals of Computation Theory","author":"E. Angel","year":"2005","unstructured":"Angel, E., Bampis, E., Gourv\u00e8s, L., Monnot, J.: (Non-)approximability for the multi-criteria TSP(1,2). In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 329\u2013340. Springer, Heidelberg (2005)"},{"key":"24_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, Heidelberg (1999)"},{"issue":"2","key":"24_CR4","doi-asserted-by":"publisher","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. Discrete Applied Mathematics\u00a016(2), 91\u201399 (1987)","journal-title":"Discrete Applied Mathematics"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1145\/1109557.1109627","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":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-540-27821-4_6","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","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.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 61\u201371. Springer, Heidelberg (2004)"},{"key":"24_CR7","unstructured":"Bl\u00e4ser, M., Manthey, B., Sgall, J.: An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. Journal of Discrete Algorithms (to appear)"},{"issue":"3","key":"24_CR8","doi-asserted-by":"publisher","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. Information Processing Letters\u00a075(3), 133\u2013138 (2000)","journal-title":"Information Processing Letters"},{"key":"24_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/3-540-45841-7_18","volume-title":"STACS 2002","author":"L. Sunil Chandran","year":"2002","unstructured":"Sunil Chandran, L., Shankar Ram, L.: Approximations for ATSP with parameterized triangle inequality. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 227\u2013237. Springer, Heidelberg (2002)"},{"key":"24_CR10","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA (1976)"},{"issue":"1","key":"24_CR11","doi-asserted-by":"publisher","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. International Transactions in Operational Research\u00a07(1), 5\u201331 (2000)","journal-title":"International Transactions in Operational Research"},{"key":"24_CR12","volume-title":"Multicriteria Optimization","author":"M. Ehrgott","year":"2005","unstructured":"Ehrgott, M.: Multicriteria Optimization. Springer, Heidelberg (2005)"},{"issue":"4","key":"24_CR13","doi-asserted-by":"publisher","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\u00a022(4), 425\u2013460 (2000)","journal-title":"OR Spectrum"},{"key":"24_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 and Company, New York (1979)"},{"issue":"4","key":"24_CR15","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H. Kaplan","year":"2005","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. Journal of the ACM\u00a052(4), 602\u2013626 (2005)","journal-title":"Journal of the ACM"},{"key":"24_CR16","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"E.L. Lawler","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons, Chichester (1985)"},{"issue":"1","key":"24_CR17","doi-asserted-by":"publisher","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\u00a07(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"issue":"2","key":"24_CR18","doi-asserted-by":"publisher","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. Journal of the ACM\u00a029(2), 285\u2013309 (1982)","journal-title":"Journal of the ACM"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1109\/SFCS.2000.892068","volume-title":"Proc. of the 41st Ann. IEEE Symp. on Foundations of Computer Science (FOCS)","author":"C.H. Papadimitriou","year":"2000","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. 86\u201392. IEEE Computer Society, Los Alamitos (2000)"},{"issue":"3","key":"24_CR20","doi-asserted-by":"publisher","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 Journal on Computing\u00a06(3), 563\u2013581 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR21","doi-asserted-by":"publisher","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. Canadian Journal of Mathematics\u00a06, 347\u2013352 (1954)","journal-title":"Canadian Journal of Mathematics"},{"key":"24_CR22","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11970125_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:23:52Z","timestamp":1619493832000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11970125_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540695134","9783540695141"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11970125_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}