{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T04:15:40Z","timestamp":1749010540787,"version":"3.41.0"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319334608"},{"type":"electronic","value":"9783319334615"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-33461-5_19","type":"book-chapter","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T22:35:59Z","timestamp":1464129359000},"page":"226-237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Constant Factor Approximation for ATSP with\u00a0Two Edge Weights"],"prefix":"10.1007","author":[{"given":"Ola","family":"Svensson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub","family":"Tarnawski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,25]]},"reference":[{"key":"19_CR1","unstructured":"Anari, N., Gharan, S.O.: Effective-resistance-reducing flows and asymmetric TSP. CoRR, abs\/1411.4613 (2014)"},{"key":"19_CR2","unstructured":"Arora, S., Grigni, M., Karger, D.R., Klein, P.N., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: Proceedings of SODA, vol. 98, pp. 33\u201341 (1998)"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An O(log n\/ log log n)-approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of SODA, pp. 379\u2013389 (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for (1, 2)-TSP. In: Proceedings of SODA, pp. 641\u2013648 (2006)","DOI":"10.1145\/1109557.1109627"},{"key":"19_CR5","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. 3122, pp. 61\u201371. Springer, Heidelberg (2004)"},{"key":"19_CR6","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, DTIC Document (1976)"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Erickson, J., Sidiropoulos, A.: A near-optimal approximation algorithm for asymmetric TSP on embedded graphs. In: Proceedings of SOCG, p. 130 (2014)","DOI":"10.1145\/2582112.2582136"},{"issue":"1","key":"19_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"AM Frieze","year":"1982","unstructured":"Frieze, A.M., Galbiati, G., Maffioli, F.: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12(1), 23\u201339 (1982)","journal-title":"Networks"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Saberi, A.: The asymmetric traveling salesman problem on graphs with bounded genus. In: Proceedings of SODA, pp. 967\u2013975. SIAM (2011)","DOI":"10.1137\/1.9781611973082.75"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of FOCS, pp. 550\u2013559 (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Grigni, M., Koutsoupias, E., Papadimitriou, C.H.: An approximation scheme for planar graph TSP. In: Proceedings of FOCS, pp. 640\u2013645 (1995)","DOI":"10.1109\/SFCS.1995.492665"},{"issue":"8","key":"19_CR12","doi-asserted-by":"publisher","first-page":"1665","DOI":"10.1016\/j.jcss.2015.06.003","volume":"81","author":"M Karpinski","year":"2015","unstructured":"Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. J. Comput. Syst. Sci. 81(8), 1665\u20131677 (2015)","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Svensson, O.: Approximating graphic TSP by matchings. In: 2011 Proceedings of FOCS, pp. 560\u2013569 (2011)","DOI":"10.1109\/FOCS.2011.56"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Mucha, M.: 13\/9-approximation for graphic TSP. In: Proceedings of STACS, pp. 30\u201341 (2012)","DOI":"10.1007\/s00224-012-9439-7"},{"issue":"1","key":"19_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"issue":"5","key":"19_CR16","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","volume":"34","author":"A Seb\u0151","year":"2014","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nicer ears: 7\/5-approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica 34(5), 597\u2013629 (2014)","journal-title":"Combinatorica"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Svensson, O.: Approximating ATSP by relaxing connectivity. In: Proceedings of FOCS (2015)","DOI":"10.1109\/FOCS.2015.10"},{"key":"19_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, New York (2011)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-33461-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T19:17:10Z","timestamp":1748978230000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-33461-5_19"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319334608","9783319334615"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-33461-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"25 May 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}