{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:14Z","timestamp":1740109274213,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2017,9,12]],"date-time":"2017-09-12T00:00:00Z","timestamp":1505174400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC Starting Grant 335288-OptApprox."],"award-info":[{"award-number":["ERC Starting Grant 335288-OptApprox."]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EPSRC First Grant EP\/M02797X\/1"],"award-info":[{"award-number":["EPSRC First Grant EP\/M02797X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s10107-017-1195-7","type":"journal-article","created":{"date-parts":[[2017,9,12]],"date-time":"2017-09-12T00:11:33Z","timestamp":1505175093000},"page":"371-397","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Constant factor approximation for ATSP with two edge weights"],"prefix":"10.1007","volume":"172","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2997-1372","authenticated-orcid":false,"given":"Ola","family":"Svensson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6175-5827","authenticated-orcid":false,"given":"Jakub","family":"Tarnawski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1152-200X","authenticated-orcid":false,"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,12]]},"reference":[{"key":"1195_CR1","unstructured":"Anari, N., Oveis Gharan, S.: Effective-resistance-reducing flows and asymmetric TSP. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE (2015)"},{"key":"1195_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 the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998, pp. 33\u201341 (1998)"},{"key":"1195_CR3","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Oveis Gharan, S., Saberi, A.: An O(log n\/ log log n)-approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 379\u2013389 (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"1195_CR4","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for (1, 2)-TSP. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 641\u2013648 (2006)","DOI":"10.1145\/1109557.1109627"},{"key":"1195_CR5","doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser, M.: A 3\/4-approximation algorithm for maximum ATSP with weights zero and one. In: Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, pp. 61\u201371 (2004)","DOI":"10.1007\/978-3-540-27821-4_6"},{"key":"1195_CR6","unstructured":"Christofides, N..: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, DTIC Document (1976)"},{"key":"1195_CR7","doi-asserted-by":"crossref","unstructured":"Erickson, J., Sidiropoulos, A.: A near-optimal approximation algorithm for asymmetric TSP on embedded graphs. In: 30th Annual Symposium on Computational Geometry (SOCG), pp. 130 (2014)","DOI":"10.1145\/2582112.2582136"},{"issue":"1","key":"1195_CR8","doi-asserted-by":"crossref","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":"1195_CR9","doi-asserted-by":"crossref","unstructured":"Oveis Gharan, S., Saberi, A.: The asymmetric traveling salesman problem on graphs with bounded genus. In: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 967\u2013975. SIAM (2011)","DOI":"10.1137\/1.9781611973082.75"},{"key":"1195_CR10","doi-asserted-by":"crossref","unstructured":"Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 550\u2013559 (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"1195_CR11","doi-asserted-by":"crossref","unstructured":"Grigni, M., Koutsoupias, E., Papadimitriou, C.H.: An approximation scheme for planar graph TSP. In: 36th Annual Symposium on Foundations of Computer Science, FOCS 1995, pp. 640\u2013645 (1995)","DOI":"10.1109\/SFCS.1995.492665"},{"key":"1195_CR12","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. J. Comput. Syst. Sci. 81(8), 1665\u20131677 (2015)","DOI":"10.1016\/j.jcss.2015.06.003"},{"key":"1195_CR13","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Svensson, O.: Approximating graphic TSP by matchings. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 560\u2013569 (2011)","DOI":"10.1109\/FOCS.2011.56"},{"key":"1195_CR14","doi-asserted-by":"crossref","unstructured":"Mucha, M.: 13\/9-approximation for graphic TSP. In: 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, pp. 30\u201341 (2012)","DOI":"10.1007\/s00224-012-9439-7"},{"key":"1195_CR15","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1\u201311 (1993)","DOI":"10.1287\/moor.18.1.1"},{"key":"1195_CR16","doi-asserted-by":"crossref","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)","DOI":"10.1007\/s00493-014-2960-3"},{"key":"1195_CR17","doi-asserted-by":"crossref","unstructured":"Svensson, O.: Approximating ATSP by relaxing connectivity. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2015)","DOI":"10.1109\/FOCS.2015.10"},{"key":"1195_CR18","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)","DOI":"10.1017\/CBO9780511921735"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1195-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1195-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1195-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T06:26:27Z","timestamp":1570083987000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1195-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,12]]},"references-count":18,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["1195"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1195-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2017,9,12]]}}}