{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:22:10Z","timestamp":1771485730759,"version":"3.50.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T00:00:00Z","timestamp":1570147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/09\/B\/ST6\/03136"],"award-info":[{"award-number":["2013\/09\/B\/ST6\/03136"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            Given a traveling salesman problem (TSP) tour\n            <jats:italic>H<\/jats:italic>\n            in graph\n            <jats:italic>G<\/jats:italic>\n            , a\n            <jats:italic>k<\/jats:italic>\n            -move is an operation that removes\n            <jats:italic>k<\/jats:italic>\n            edges from\n            <jats:italic>H<\/jats:italic>\n            and adds\n            <jats:italic>k<\/jats:italic>\n            edges of\n            <jats:italic>G<\/jats:italic>\n            so that a new tour\n            <jats:italic>H<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            is formed. The popular\n            <jats:italic>k<\/jats:italic>\n            -OPT heuristic for TSP finds a local optimum by starting from an arbitrary tour\n            <jats:italic>H<\/jats:italic>\n            and then improving it by a sequence of\n            <jats:italic>k<\/jats:italic>\n            -moves.\n          <\/jats:p>\n          <jats:p>\n            Until 2016, the only known algorithm to find an improving\n            <jats:italic>k<\/jats:italic>\n            -move for a given tour was the naive solution in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ). At ICALP\u201916, de\u00a0Berg, Buchin, Jansen, and Woeginger showed an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u230a2\n              <jats:italic>k<\/jats:italic>\n              \/3\u230b+1\n            <\/jats:sup>\n            )-time algorithm.\n          <\/jats:p>\n          <jats:p>\n            We show an algorithm that runs in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              (1\/4+\u03f5\n              <jats:sub>\n                <jats:italic>k<\/jats:italic>\n              <\/jats:sub>\n              )\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) time, where lim\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n              \u2192 \u221e\n            <\/jats:sub>\n            \u03f5\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            = 0. It improves over the state of the art for every\n            <jats:italic>k<\/jats:italic>\n            \u2265 5. For the most practically relevant case\n            <jats:italic>k<\/jats:italic>\n            = 5, we provide a slightly refined algorithm running in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3.4<\/jats:sup>\n            ) time. We also show that for the\n            <jats:italic>k<\/jats:italic>\n            = 4 case, improving over the\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            )-time algorithm of de Berg et al. would be a major breakthrough: An\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\u2212\u03f5<\/jats:sup>\n            )-time algorithm for any \u03f5 &gt; 0 would imply an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\u2212\u03b4<\/jats:sup>\n            )-time algorithm for the A\n            <jats:sc>ll<\/jats:sc>\n            P\n            <jats:sc>airs<\/jats:sc>\n            S\n            <jats:sc>hortest<\/jats:sc>\n            P\n            <jats:sc>aths<\/jats:sc>\n            problem, for some \u03b4 &gt; 0.\n          <\/jats:p>","DOI":"10.1145\/3341730","type":"journal-article","created":{"date-parts":[[2019,10,7]],"date-time":"2019-10-07T12:20:59Z","timestamp":1570450859000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Improving TSP Tours Using Dynamic Programming over Tree Decompositions"],"prefix":"10.1145","volume":"15","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Banacha, Warszawa, Poland"}]},{"given":"\u0141ukasz","family":"Kowalik","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Banacha, Warszawa, Poland"}]},{"given":"Arkadiusz","family":"Soca\u0142a","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Banacha, Warszawa, Poland"}]}],"member":"320","published-online":{"date-parts":[[2019,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_2_1","article-title":"On exact algorithms for treewidth","volume":"9","author":"Bodlaender Hans L.","year":"2012","unstructured":"Hans L. Bodlaender , Fedor V. Fomin , Arie M. C. A. Koster , Dieter Kratsch , and Dimitrios M. Thilikos . 2012 . On exact algorithms for treewidth . ACM Trans. Algor. 9 , 1 (2012), 12:1--12:23. Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. 2012. On exact algorithms for treewidth. ACM Trans. Algor. 9, 1 (2012), 12:1--12:23.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251244"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.6.791"},{"key":"e_1_2_1_6_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201916)","volume":"55","author":"de Berg Mark","unstructured":"Mark de Berg , Kevin Buchin , Bart M. P. Jansen , and Gerhard J. Woeginger . 2016. Fine-grained complexity analysis of two classic TSP variants . In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201916) , LIPIcs, Vol. 55 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 5:1--5:14. Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard J. Woeginger. 2016. Fine-grained complexity analysis of two classic TSP variants. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201916), LIPIcs, Vol. 55. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 5:1--5:14."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9133-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1138831.1711171"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics (LIPIcs)), Jean-Yves Marion and Thomas Schwentick (Eds.)","volume":"5","author":"Fedor","year":"2010","unstructured":"Fedor V. Fomin and Yngve Villanger. 2010. Finding induced subgraphs via minimal triangulations . In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics (LIPIcs)), Jean-Yves Marion and Thomas Schwentick (Eds.) , Vol. 5 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 383--394. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.STACS. 2010 .2470 10.4230\/LIPIcs.STACS.2010.2470 Fedor V. Fomin and Yngve Villanger. 2010. Finding induced subgraphs via minimal triangulations. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics (LIPIcs)), Jean-Yves Marion and Thomas Schwentick (Eds.), Vol. 5. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 383--394. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2010.2470"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9685-8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0110015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00284-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90044-X"},{"key":"e_1_2_1_16_1","volume-title":"Lecture Notes in Computer Science","author":"Kloks Ton","unstructured":"Ton Kloks . 1994. Treewidth, Computations and Approximations . Lecture Notes in Computer Science , Vol. 842 . Springer . Ton Kloks. 1994. Treewidth, Computations and Approximations. Lecture Notes in Computer Science, Vol. 842. Springer."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219052"},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201915)","author":"K\u00fcnnemann Marvin","unstructured":"Marvin K\u00fcnnemann and Bodo Manthey . 2015. Towards understanding the smoothed approximation ratio of the 2-opt heuristic . In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201915) , Lecture Notes in Computer Science , Vol. 9134 . Springer , 859--871. Marvin K\u00fcnnemann and Bodo Manthey. 2015. Towards understanding the smoothed approximation ratio of the 2-opt heuristic. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201915), Lecture Notes in Computer Science, Vol. 9134. Springer, 859--871."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1965.tb04146.x"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"e_1_2_1_21_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the International Society for Augmentative and Alternative Communication (ISAAC\u201913)","author":"Manthey Bodo","unstructured":"Bodo Manthey and Rianne Veenstra . 2013. Smoothed analysis of the 2-opt heuristic for the TSP: Polynomial bounds for Gaussian noise . In Proceedings of the International Society for Augmentative and Alternative Communication (ISAAC\u201913) . Lecture Notes in Computer Science , Vol. 8283 . Springer , 579--589. Bodo Manthey and Rianne Veenstra. 2013. Smoothed analysis of the 2-opt heuristic for the TSP: Polynomial bounds for Gaussian noise. In Proceedings of the International Society for Augmentative and Alternative Communication (ISAAC\u201913). Lecture Notes in Computer Science, Vol. 8283. Springer, 579--589."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.02.008"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1033004"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2960-3"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341730","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341730","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:24Z","timestamp":1750207404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341730"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,4]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3341730"],"URL":"https:\/\/doi.org\/10.1145\/3341730","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,4]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}