{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T16:40:42Z","timestamp":1764002442755,"version":"3.45.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100002341","name":"Research Council of Finland","doi-asserted-by":"crossref","award":["363444"],"award-info":[{"award-number":["363444"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["853234"],"award-info":[{"award-number":["853234"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["559177164"],"award-info":[{"award-number":["559177164"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>\n                    We revisit the classic task of finding the shortest tour of\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    points in\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    -dimensional Euclidean space, for any fixed constant\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    \u2a7e 2. We determine the optimal dependence on \u025b in the running time of an algorithm that computes a (1 + \u025b)-approximate tour, under a plausible assumption. Specifically, we give an algorithm that runs in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2^{\\mathcal {O}(1\/\\varepsilon ^{d-1})} n\\log n\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    time. This improves the previously smallest dependence on \u025b in the running time\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((1\/\\varepsilon)^{\\mathcal {O}(1\/\\varepsilon ^{d-1})}n \\log n\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    of the algorithm by Rao and Smith\u00a0(STOC 1998). We also show that a\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2^{o(1\/\\varepsilon ^{d-1})}\\mathrm{poly}(n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    algorithm would violate the Gap-Exponential Time Hypothesis (Gap-ETH).\n                  <\/jats:p>\n                  <jats:p>\n                    Our new algorithm builds upon the celebrated quadtree-based methods initially proposed by Arora (J. ACM 1998), but it adds a new idea that we call\n                    <jats:italic toggle=\"yes\">sparsity-sensitive patching<\/jats:italic>\n                    . On a high level this lets the granularity with which we simplify the tour depend on how sparse it is locally. We demonstrate that our technique extends to other problems, by showing that for Steiner Tree and Rectilinear Steiner Tree it yields the same running time. We complement our results with a matching Gap-ETH lower bound for Rectilinear Steiner Tree.\n                  <\/jats:p>","DOI":"10.1145\/3766548","type":"journal-article","created":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T13:40:14Z","timestamp":1757338814000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Gap-ETH-Tight Approximation Scheme for Euclidean TSP"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6856-2902","authenticated-orcid":false,"given":"S\u00e1ndor","family":"Kisfaludi-Bak","sequence":"first","affiliation":[{"name":"Aalto University","place":["Espoo, Finland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":false,"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Utrecht University","place":["Utrecht, Netherlands"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9746-5733","authenticated-orcid":false,"given":"Karol","family":"W\u0119grzycki","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity, Max Planck Institute for Informatics","place":["Saarbr\u00fccken, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,24]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"issue":"1","key":"e_1_3_4_3_2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s10107-003-0438-y","article-title":"Approximation schemes for NP-hard geometric optimization problems: A survey","volume":"97","author":"Arora Sanjeev","year":"2003","unstructured":"Sanjeev Arora. 2003. Approximation schemes for NP-hard geometric optimization problems: A survey. Math. Program. 97, 1-2 (2003), 43\u201369.","journal-title":"Math. Program."},{"key":"e_1_3_4_4_2","first-page":"33","volume-title":"Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 25-27 January 1998, San Francisco, California, USA","author":"Arora Sanjeev","year":"1998","unstructured":"Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, and Andrzej Woloszyn. 1998. A polynomial-time approximation scheme for weighted planar graph TSP. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 25-27 January 1998, San Francisco, California, USA. 33\u201341. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=314613.314632"},{"key":"e_1_3_4_5_2","first-page":"33","volume-title":"Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998)","author":"Arora Sanjeev","year":"1998","unstructured":"Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, and Andrzej Woloszyn. 1998. A polynomial-time approximation scheme for weighted planar graph TSP. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998). 33\u201341."},{"key":"e_1_3_4_6_2","first-page":"106","volume-title":"Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998","author":"Arora Sanjeev","year":"1998","unstructured":"Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. 1998. Approximation schemes for euclidean k-medians and related problems. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998. 106\u2013113. DOI:10.1145\/276698.276718"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.80"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/130913328"},{"key":"e_1_3_4_10_2","first-page":"15:1\u201315:17","volume-title":"37th International Symposium on Computational Geometry (SoCG 2021)","author":"Bhore Sujoy","year":"2021","unstructured":"Sujoy Bhore and Csaba D. T\u00f3th. 2021. Light Euclidean steiner spanners in the plane. In 37th International Symposium on Computational Geometry (SoCG 2021), Vol. 189. 15:1\u201315:17."},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629654"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.76"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158232"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.02.008"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.03.005"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3148227"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055093"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_83"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009183"},{"key":"e_1_3_4_21_2","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1109\/FOCS.2018.00050","volume-title":"Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018)","author":"Berg Mark de","year":"2018","unstructured":"Mark de Berg, Hans L. Bodlaender, S\u00e1ndor Kisfaludi-Bak, and Sudeshna Kolay. 2018. An ETH-tight exact algorithm for euclidean TSP. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018). IEEE Computer Society, 450\u2013461. DOI:10.1109\/FOCS.2018.00050"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1320870"},{"key":"e_1_3_4_23_2","first-page":"441","volume-title":"Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC 2011)","author":"Demaine Erik D.","year":"2011","unstructured":"Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. 2011. Contraction decomposition in H-minor-free graphs and algorithmic applications. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC 2011). 441\u2013450. DOI:10.1145\/1993636.1993696"},{"key":"e_1_3_4_24_2","first-page":"128","article-title":"Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover","volume":"23","author":"Dinur Irit","year":"2016","unstructured":"Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electron. Colloquium Comput. Complex. 23 (2016), 128. Retrieved from http:\/\/eccc.hpi-web.de\/report\/2016\/128","journal-title":"Electron. Colloquium Comput. Complex."},{"issue":"3","key":"e_1_3_4_25_2","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","article-title":"The steiner problem in graphs","volume":"1","author":"Dreyfus Stuart E.","year":"1971","unstructured":"Stuart E. Dreyfus and Robert A. Wagner. 1971. The steiner problem in graphs. Networks 1, 3 (1971), 195\u2013207.","journal-title":"Networks"},{"key":"e_1_3_4_26_2","first-page":"1433","volume-title":"Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023","author":"Dross Fran\u00e7ois","year":"2023","unstructured":"Fran\u00e7ois Dross, Krzysztof Fleszar, Karol Wegrzycki, and Anna Zych-Pawlewicz. 2023. Gap-ETH-tight approximation schemes for red-green-blue separation and bicolored noncrossing euclidean travelling salesman tours. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, Nikhil Bansal and Viswanath Nagarajan (Eds.). SIAM, 1433\u20131463. DOI:10.1137\/1.9781611977554.CH52"},{"issue":"6","key":"e_1_3_4_27_2","doi-asserted-by":"crossref","first-page":"146","DOI":"10.3390\/a13060146","article-title":"A survey on approximation in parameterized complexity: Hardness and algorithms","volume":"13","author":"Feldmann Andreas Emil","year":"2020","unstructured":"Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. 2020. A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms 13, 6 (2020), 146.","journal-title":"Algorithms"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1210678"},{"issue":"4","key":"e_1_3_4_29_2","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","article-title":"The rectilinear Steiner tree problem is NP-complete","volume":"32","author":"Garey Michael R","year":"1977","unstructured":"Michael R Garey and David S. Johnson. 1977. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 4 (1977), 826\u2013834.","journal-title":"SIAM J. Appl. Math."},{"key":"e_1_3_4_30_2","doi-asserted-by":"crossref","unstructured":"Y. Bartal and L.-A. Gottlieb. 2021. Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 1028\u20131041.","DOI":"10.1145\/3406325.3451063"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492665"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492665"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"issue":"2","key":"e_1_3_4_34_2","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0114025","article-title":"On steiner\u2019s problem with rectilinear distance","volume":"14","author":"Hanan Maurice","year":"1966","unstructured":"Maurice Hanan. 1966. On steiner\u2019s problem with rectilinear distance. SIAM J. Appl. Math. 14, 2 (1966), 255\u2013265.","journal-title":"SIAM J. Appl. Math."},{"key":"e_1_3_4_35_2","volume-title":"Geometric Approximation Algorithms","author":"Har-Peled Sariel","year":"2011","unstructured":"Sariel Har-Peled. 2011. Geometric Approximation Algorithms. American Mathematical Society, USA."},{"issue":"4","key":"e_1_3_4_36_2","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0211056","article-title":"Hamilton paths in grid graphs","volume":"11","author":"Itai Alon","year":"1982","unstructured":"Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter. 1982. Hamilton paths in grid graphs. SIAM J. Comput. 11, 4 (1982), 676\u2013686.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_4_37_2","volume-title":"ETH-Tight Algorithms for Geometric Network Problems","author":"Kisfaludi-Bak S\u00e1ndor","year":"2019","unstructured":"S\u00e1ndor Kisfaludi-Bak. 2019. ETH-Tight Algorithms for Geometric Network Problems. Ph.D. Dissertation. Technische Universiteit Eindhoven, Department of Mathematics and Computer Science. Retrieved fromhttps:\/\/research.tue.nl\/en\/publications\/eth-tight-algorithms-for-geometric-network-problems"},{"key":"e_1_3_4_38_2","first-page":"749","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006)","author":"Klein Philip N.","year":"2006","unstructured":"Philip N. Klein. 2006. A subset spanner for planar graphs, with application to subset TSP. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006). 749\u2013756. DOI:10.1145\/1132516.1132620"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/060649562"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702404055"},{"key":"e_1_3_4_41_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial Optimization: Theory and Algorithms (5th ed.)","author":"Korte Bernhard","year":"2012","unstructured":"Bernhard Korte and Jens Vygen. 2012. Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Publishing Company, Incorporated."},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.9"},{"key":"e_1_3_4_43_2","first-page":"2279","volume-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)","author":"Le Hung","year":"2020","unstructured":"Hung Le. 2020. A PTAS for subset TSP in minor-free graphs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020). 2279\u20132298. DOI:10.1137\/1.9781611975994.140"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00069"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2020.67"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.78"},{"key":"e_1_3_4_48_2","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1109\/FOCS.2007.26","volume-title":"48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007)","author":"Marx D\u00e1niel","year":"2007","unstructured":"D\u00e1niel Marx. 2007. On the optimality of planar and geometric approximation schemes. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007). 338\u2013348."},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_3_4_50_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"Narasimhan Giri","year":"2007","unstructured":"Giri Narasimhan and Michiel H. M. Smid. 2007. Geometric Spanner Networks. Cambridge University Press."},{"key":"e_1_3_4_51_2","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","year":"1994","unstructured":"Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley."},{"issue":"4","key":"e_1_3_4_52_2","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","article-title":"The NP-completeness of the hamiltonian cycle problem in planar diagraphs with degree bound two","volume":"8","author":"Plesn\u00edk J\u00e1n","year":"1979","unstructured":"J\u00e1n Plesn\u00edk. 1979. The NP-completeness of the hamiltonian cycle problem in planar diagraphs with degree bound two. Inform. Process. Lett. 8, 4 (1979), 199\u2013201.","journal-title":"Inform. Process. Lett."},{"key":"e_1_3_4_53_2","first-page":"540","volume-title":"Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC 1998)","author":"Rao Satish","year":"1998","unstructured":"Satish Rao and Warren D. Smith. 1998. Approximating geometrical graphs via \u201cSpanners\u201d and \u201cBanyans\u201d. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC 1998). ACM, 540\u2013550. DOI:10.1145\/276698.276868"},{"key":"e_1_3_4_54_2","first-page":"250","volume-title":"Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, New York, USA, June 6-8, 1994","author":"Robins Gabriel","year":"1994","unstructured":"Gabriel Robins and Jeffrey S. Salowe. 1994. On the maximum degree of minimum spanning trees. In Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, New York, USA, June 6-8, 1994, Kurt Mehlhorn (Ed.). ACM, 250\u2013258. DOI:10.1145\/177424.177978"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221013"},{"key":"e_1_3_4_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799352735"},{"key":"e_1_3_4_57_2","first-page":"81:1\u201381:12","volume-title":"40th International Symposium on Computational Geometry (SoCG 2024) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"293","author":"Wijland Ernest van","year":"2024","unstructured":"Ernest van Wijland and Hang Zhou. 2024. Faster approximation scheme for euclidean k-TSP. In 40th International Symposium on Computational Geometry (SoCG 2024) (Leibniz International Proceedings in Informatics (LIPIcs)). Wolfgang Mulzer and Jeff M. Phillips (Eds.), Vol. 293. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 81:1\u201381:12. DOI:10.4230\/LIPIcs.SoCG.2024.81"},{"key":"e_1_3_4_58_2","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","year":"2004","unstructured":"Vijay V. Vazirani. 2004. Approximation Algorithms. Springer."},{"key":"e_1_3_4_59_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"Williamson David P.","year":"2011","unstructured":"David P. Williamson and David B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3766548","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T16:34:16Z","timestamp":1764002056000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3766548"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,24]]},"references-count":58,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3766548"],"URL":"https:\/\/doi.org\/10.1145\/3766548","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2025,11,24]]},"assertion":[{"value":"2024-08-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}