{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T21:27:59Z","timestamp":1673299679692},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["335288?OptApprox,757481?ScaleOpt"]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"crossref","award":["200021-184656"]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M02797X\/1"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.<\/jats:p>\n The main idea of our approach is a reduction to Subtour Partition Cover, an easier problem obtained by significantly relaxing the general connectivity requirements into local connectivity conditions. We first show that any algorithm for Subtour Partition Cover can be turned into an algorithm for ATSP while only losing a small constant factor in the performance guarantee. Next, we present a reduction from general ATSP instances to structured instances, on which we then solve Subtour Partition Cover, yielding our constant-factor approximation algorithm for ATSP.<\/jats:p>","DOI":"10.1145\/3424306","type":"journal-article","created":{"date-parts":[[2020,11,3]],"date-time":"2020-11-03T23:05:31Z","timestamp":1604444731000},"page":"1-53","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem"],"prefix":"10.1145","volume":"67","author":[{"given":"Ola","family":"Svensson","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland"}]},{"given":"Jakub","family":"Tarnawski","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland"}]},{"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"additional","affiliation":[{"name":"London School of Economics and Political Science, London, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2020,11,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818310"},{"key":"e_1_2_1_2_1","volume-title":"Shmoys","author":"An Hyung-Chan","year":"2010","unstructured":"Hyung-Chan An , Robert D. Kleinberg , and David B . Shmoys . 2010 . Approximation algorithms for the bottleneck asymmetric traveling salesman problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer , 1--11. Hyung-Chan An, Robert D. Kleinberg, and David B. Shmoys. 2010. Approximation algorithms for the bottleneck asymmetric traveling salesman problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 1--11."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.11"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Symposium on Mathematical Programming.","author":"Arthanari T. S.","year":"1982","unstructured":"T. S. Arthanari . 1982 . On the traveling salesman problem . In Proceedings of the Symposium on Mathematical Programming. T. S. Arthanari. 1982. On the traveling salesman problem. In Proceedings of the Symposium on Mathematical Programming."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3216622.3216635"},{"key":"e_1_2_1_6_1","article-title":"A new approximation algorithm for the asymmetric TSP with triangle inequality","volume":"4","author":"Bl\u00e4ser Markus","year":"2008","unstructured":"Markus Bl\u00e4ser . 2008 . A new approximation algorithm for the asymmetric TSP with triangle inequality . ACM Trans. Algor. 4 , 4 (2008). Markus Bl\u00e4ser. 2008. A new approximation algorithm for the asymmetric TSP with triangle inequality. ACM Trans. Algor. 4, 4 (2008).","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Robert Carr. 1996. Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time. In Integer Programming and Combinatorial Optimization William H. Cunningham S. Thomas McCormick and Maurice Queyranne (Eds.). Springer Berlin 460--474. Robert Carr. 1996. Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time. In Integer Programming and Combinatorial Optimization William H. Cunningham S. Thomas McCormick and Maurice Queyranne (Eds.). Springer Berlin 460--474.","DOI":"10.1007\/3-540-61310-2_34"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0191"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582008"},{"key":"e_1_2_1_11_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Technique","author":"Feige Uriel","unstructured":"Uriel Feige and Mohit Singh . 2007. Improved approximation ratios for traveling salesperson tours and paths in directed graphs . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Technique . Springer , 104--118. Uriel Feige and Mohit Singh. 2007. Improved approximation ratios for traveling salesperson tours and paths in directed graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Technique. Springer, 104--118."},{"key":"e_1_2_1_12_1","first-page":"29","article-title":"The square of every two-connected graph is Hamiltonian. J. Combin. Theor","volume":"16","author":"Fleischner Herbert","year":"1974","unstructured":"Herbert Fleischner . 1974 . The square of every two-connected graph is Hamiltonian. J. Combin. Theor ., Series B 16 , 1 (1974), 29 -- 34 . Herbert Fleischner. 1974. The square of every two-connected graph is Hamiltonian. J. Combin. Theor., Series B 16, 1 (1974), 29--34.","journal-title":"Series B"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120103"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.75"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.80"},{"key":"e_1_2_1_16_1","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin","unstructured":"Martin Gr\u00f6tschel , L\u00e1szl\u00f3 Lov\u00e1sz , and Alexander Schrijver . 2012. Geometric Algorithms and Combinatorial Optimization . Vol. 2 . Springer Science 8 Business Media. Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 2012. Geometric Algorithms and Combinatorial Optimization. Vol. 2. Springer Science 8 Business Media."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082041"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45030-3_53"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00160-3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01450-8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01564847"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2739008"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","author":"Mucha Marcin","year":"2012","unstructured":"Marcin Mucha . 2012 . 13\/9-approximation for graphic TSP . In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912) . 30--41. Marcin Mucha. 2012. 13\/9-approximation for graphic TSP. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912). 30--41."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(84)90077-4"},{"key":"e_1_2_1_25_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 1998. Theory of Linear and Integer Programming . John Wiley 8 Sons, New York. Alexander Schrijver. 1998. Theory of Linear and Integer Programming. John Wiley 8 Sons, New York."},{"key":"e_1_2_1_26_1","volume-title":"Combinatorial Optimization\u2014Polyhedra and Efficiency","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 2003. Combinatorial Optimization\u2014Polyhedra and Efficiency . Springer-Verlag , Berlin . Alexander Schrijver. 2003. Combinatorial Optimization\u2014Polyhedra and Efficiency. Springer-Verlag, Berlin."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2960-3"},{"key":"e_1_2_1_28_1","first-page":"76","article-title":"On some extremal tours in graphs (in Russian)","volume":"17","author":"Serdyukov Anatoliy I.","year":"1978","unstructured":"Anatoliy I. Serdyukov . 1978 . On some extremal tours in graphs (in Russian) . Upravl. Syst. 17 (1978), 76 -- 79 . Anatoliy I. Serdyukov. 1978. On some extremal tours in graphs (in Russian). Upravl. Syst. 17 (1978), 76--79.","journal-title":"Upravl. Syst."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.10"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 50th ACM SIGACT Symposium on Theory of Computing (STOC\u201918)","author":"Svensson Ola","unstructured":"Ola Svensson , Jakub Tarnawski , and L\u00e1szl\u00f3 A. V\u00e9gh . 2018. A constant-factor approximation algorithm for the asymmetric traveling salesman problem . In Proceedings of the 50th ACM SIGACT Symposium on Theory of Computing (STOC\u201918) . 204--213. Ola Svensson, Jakub Tarnawski, and L\u00e1szl\u00f3 A. V\u00e9gh. 2018. A constant-factor approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of the 50th ACM SIGACT Symposium on Theory of Computing (STOC\u201918). 204--213."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1195-7"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384233"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.001"},{"key":"e_1_2_1_34_1","volume-title":"Slugina","author":"van Bevern Ren\u00e9","year":"2020","unstructured":"Ren\u00e9 van Bevern and Viktoriia A . Slugina . 2020 . A historical note on the 3\/2-approximation algorithm for the metric traveling salesman problem. Hist. Math . (2020). DOI:https:\/\/doi.org\/10.1016\/j.hm.2020.04.003 10.1016\/j.hm.2020.04.003 Ren\u00e9 van Bevern and Viktoriia A. Slugina. 2020. A historical note on the 3\/2-approximation algorithm for the metric traveling salesman problem. Hist. Math. (2020). DOI:https:\/\/doi.org\/10.1016\/j.hm.2020.04.003"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999)","author":"Vempala Santosh","year":"1999","unstructured":"Santosh Vempala and Mihalis Yannakakis . 1999 . A convex relaxation for the asymmetric TSP . In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999) . 975--976. Santosh Vempala and Mihalis Yannakakis. 1999. A convex relaxation for the asymmetric TSP. In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999). 975--976."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3424306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T18:32:13Z","timestamp":1672597933000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3424306"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,3]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3424306"],"URL":"http:\/\/dx.doi.org\/10.1145\/3424306","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2020,11,3]]},"assertion":[{"value":"2019-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}