{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:24:41Z","timestamp":1725582281123},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208768"},{"type":"electronic","value":"9783642208775"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20877-5_27","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T02:35:17Z","timestamp":1303871717000},"page":"264-275","source":"Crossref","is-referenced-by-count":3,"title":["Deterministic Algorithms for Multi-criteria TSP"],"prefix":"10.1007","author":[{"given":"Bodo","family":"Manthey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-3","key":"27_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-3), 135\u2013146 (2004)","journal-title":"Theoretical Computer Science"},{"key":"27_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":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-540-85363-3_23","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Arvind","year":"2008","unstructured":"Arvind, V., Mukhopadhyay, P.: Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 276\u2013289. Springer, Heidelberg (2008)"},{"key":"27_CR4","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1137\/1.9781611973075.32","volume-title":"Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"A. Asadpour","year":"2010","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An O(logn\/loglogn)-approximation algorithm for the asymmetric traveling salesman problem. In: Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 379\u2013389. SIAM, Philadelphia (2010)"},{"key":"27_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Heidelberg (1999)"},{"key":"27_CR6","first-page":"641","volume-title":"Proc. 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. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 641\u2013648. SIAM, Philadelphia (2006)"},{"key":"27_CR7","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)"},{"issue":"2","key":"27_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s00453-004-1131-0","volume":"42","author":"M. Bl\u00e4ser","year":"2005","unstructured":"Bl\u00e4ser, M., Manthey, B.: Approximating maximum weight cycle covers in directed graphs with weights zero and one. Algorithmica\u00a042(2), 121\u2013139 (2005)","journal-title":"Algorithmica"},{"issue":"4","key":"27_CR9","doi-asserted-by":"publisher","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. Journal of Discrete Algorithms\u00a04(4), 623\u2013632 (2006)","journal-title":"Journal of Discrete Algorithms"},{"issue":"3","key":"27_CR10","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"},{"issue":"1-3","key":"27_CR11","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.tcs.2006.10.026","volume":"370","author":"L. Sunil Chandran","year":"2007","unstructured":"Sunil Chandran, L., Shankar Ram, L.: On the relationship between ATSP and the cycle cover problem. Theoretical Computer Science\u00a0370(1-3), 218\u2013228 (2007)","journal-title":"Theoretical Computer Science"},{"key":"27_CR12","volume-title":"Multicriteria Optimization","author":"M. Ehrgott","year":"2005","unstructured":"Ehrgott, M.: Multicriteria Optimization. Springer, Heidelberg (2005)"},{"key":"27_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-540-74208-1_8","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"U. Feige","year":"2007","unstructured":"Feige, U., Singh, M.: Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 104\u2013118. Springer, Heidelberg (2007)"},{"key":"27_CR14","unstructured":"Gla\u00dfer, C., Reitwie\u00dfner, C., Witek, M.: Balanced combinations of solutions in multi-objective optimization, arXiv:1007.5475v1 [cs.DS] (2010)"},{"key":"27_CR15","unstructured":"Gla\u00dfer, C., Reitwie\u00dfner, C., Witek, M.: Improved and derandomized approximations for two-criteria metric traveling salesman. Report 09-076, Rev. 1, Electron. Colloq. on Computational Complexity (ECCC) (2010)"},{"key":"27_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-642-04128-0_9","volume-title":"Algorithms - ESA 2009","author":"F. Grandoni","year":"2009","unstructured":"Grandoni, F., Ravi, R., Singh, M.: Iterative Rounding for Multi-Objective Optimization Problems. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 95\u2013106. Springer, Heidelberg (2009)"},{"issue":"4","key":"27_CR17","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.I.: 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":"27_CR18","unstructured":"Manthey, B.: On approximating multi-criteria TSP. In: Proc. 26th Int. Symp. on Theoretical Aspects of Computer Science (STACS), pp. 637\u2013648 (2009)"},{"key":"27_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-642-12450-1_19","volume-title":"Approximation and Online Algorithms","author":"B. Manthey","year":"2010","unstructured":"Manthey, B.: Multi-criteria TSP: Min and max combined. In: Bampis, E., Jansen, K. (eds.) WAOA 2009. LNCS, vol.\u00a05893, pp. 205\u2013216. Springer, Heidelberg (2010)"},{"issue":"1","key":"27_CR20","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00453-007-9011-z","volume":"53","author":"B. Manthey","year":"2009","unstructured":"Manthey, B., Shankar Ram, L.: Approximation algorithms for multi-criteria traveling salesman problems. Algorithmica\u00a053(1), 69\u201388 (2009)","journal-title":"Algorithmica"},{"issue":"1","key":"27_CR21","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"},{"key":"27_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/978-3-642-03685-9_23","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"K. Paluch","year":"2009","unstructured":"Paluch, K., Mucha, M., M\u0105dry, A.: A 7\/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 298\u2013311. Springer, Heidelberg (2009)"},{"issue":"2","key":"27_CR23","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of restricted spanning tree problems. Journal of the ACM\u00a029(2), 285\u2013309 (1982)","journal-title":"Journal of the ACM"},{"key":"27_CR24","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1109\/SFCS.2000.892068","volume-title":"Proc. 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. 41st Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 86\u201392. IEEE, Los Alamitos (2000)"},{"issue":"2-3","key":"27_CR25","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.jalgor.2008.10.002","volume":"64","author":"T. Zhang","year":"2009","unstructured":"Zhang, T., Li, W., Li, J.: An improved approximation algorithm for the ATSP with parameterized triangle inequality. Journal of Algorithms\u00a064(2-3), 74\u201378 (2009)","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20877-5_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T01:13:40Z","timestamp":1558574020000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20877-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208768","9783642208775"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20877-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}