{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:34:12Z","timestamp":1760441652463,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T00:00:00Z","timestamp":1609372800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,1,31]]},"abstract":"<jats:p>\n            We analyze two classic variants of the T\n            <jats:sc>RAVELING<\/jats:sc>\n            S\n            <jats:sc>ALESMAN<\/jats:sc>\n            P\n            <jats:sc>ROBLEM<\/jats:sc>\n            (\n            <jats:sc>TSP<\/jats:sc>\n            ) using the toolkit of fine-grained complexity.\n          <\/jats:p>\n          <jats:p>\n            Our first set of results is motivated by the B\n            <jats:sc>ITONIC TSP<\/jats:sc>\n            problem: given a set of\u00a0\n            <jats:italic>n<\/jats:italic>\n            points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamic-programming exercise to solve this problem in\u00a0\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time. While the near-quadratic dependency of similar dynamic programs for L\n            <jats:sc>ONGEST<\/jats:sc>\n            C\n            <jats:sc>OMMON<\/jats:sc>\n            S\n            <jats:sc>UBSEQUENCE<\/jats:sc>\n            and D\n            <jats:sc>ISCRETE<\/jats:sc>\n            F\n            <jats:sc>r\u00e9chet<\/jats:sc>\n            D\n            <jats:sc>istance<\/jats:sc>\n            has recently been proven to be essentially optimal under the Strong Exponential Time Hypothesis, we show that bitonic tours can be found in subquadratic time. More precisely, we present an algorithm that solves bitonic TSP in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time and its bottleneck version in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>3<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time. In the more general pyramidal TSP problem, the points to be visited are labeled 1,\u2026 ,\n            <jats:italic>n<\/jats:italic>\n            and the sequence of labels in the solution is required to have at most one local maximum. Our algorithms for the bitonic (bottleneck) TSP problem also work for the pyramidal TSP problem in the plane.\n          <\/jats:p>\n          <jats:p>\n            Our second set of results concerns the popular\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>OPT<\/jats:sc>\n            heuristic for TSP in the graph setting. More precisely, we study the\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>OPT<\/jats:sc>\n            decision problem, which asks whether a given tour can be improved by a\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>OPT<\/jats:sc>\n            move that replaces\n            <jats:italic>k<\/jats:italic>\n            edges in the tour by\n            <jats:italic>k<\/jats:italic>\n            new edges. A simple algorithm solves\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>OPT<\/jats:sc>\n            in\u00a0\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            ) time for fixed\u00a0\n            <jats:italic>k<\/jats:italic>\n            . For 2-\n            <jats:sc>OPT<\/jats:sc>\n            , this is easily seen to be optimal. For\u00a0\n            <jats:italic>k<\/jats:italic>\n            =3, we prove that an algorithm with a runtime of the form\u00a0\u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\u2212\u025b<\/jats:sup>\n            ) exists if and only if 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            in weighted digraphs has such an algorithm. For general\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>OPT<\/jats:sc>\n            , it is known that a runtime of\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ) \u00b7\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              \/ log\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            would contradict the Exponential Time Hypothesis. The results for\n            <jats:italic>k<\/jats:italic>\n            =2,3 may suggest that the actual time complexity of\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>OPT<\/jats:sc>\n            is \u0398 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ). We show that this is not the case, by presenting an algorithm that finds the best\n            <jats:italic>k<\/jats:italic>\n            -move in\u00a0\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u230a 2\n              <jats:italic>k<\/jats:italic>\n              \/3 \u230b+1\n            <\/jats:sup>\n            ) time for fixed\u00a0\n            <jats:italic>k<\/jats:italic>\n            \u2265 3. This implies that 4-\n            <jats:sc>OPT<\/jats:sc>\n            can be solved in\u00a0\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ) time, matching the best-known algorithm for 3-\n            <jats:sc>OPT<\/jats:sc>\n            . Finally, we show how to beat the quadratic barrier for\n            <jats:italic>k<\/jats:italic>\n            =2 in two important settings, namely, for points in the plane and when we want to solve 2-\n            <jats:sc>OPT<\/jats:sc>\n            repeatedly.\n          <\/jats:p>","DOI":"10.1145\/3414845","type":"journal-article","created":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T18:48:01Z","timestamp":1609440481000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Fine-grained Complexity Analysis of Two Classic TSP Variants"],"prefix":"10.1145","volume":"17","author":[{"given":"Mark de","family":"Berg","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, the Netherlands"}]},{"given":"Kevin","family":"Buchin","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, the Netherlands"}]},{"given":"Bart M. P.","family":"Jansen","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, the Netherlands"}]},{"given":"Gerhard","family":"Woeginger","sequence":"additional","affiliation":[{"name":"Department of Computer Science, RWTH Aachen University, Aachen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2020,12,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722241"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746594"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574015"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/120890855"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1388"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(98)00067-7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808735"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320186"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 27th ESA (LIPIcs), Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.)","volume":"144","author":"Bonnet \u00c9douard","year":"2019","unstructured":"\u00c9douard Bonnet , Yoichi Iwata , Bart M. P. Jansen , and Lukasz Kowalik . 2019 . Fine-grained complexity of k-Opt in Bounded-Degree Graphs for Solving TSP . In Proceedings of the 27th ESA (LIPIcs), Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.) , Vol. 144 . 23:1--23:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.23 10.4230\/LIPIcs.ESA.2019.23 \u00c9douard Bonnet, Yoichi Iwata, Bart M. P. Jansen, and Lukasz Kowalik. 2019. Fine-grained complexity of k-Opt in Bounded-Degree Graphs for Solving TSP. In Proceedings of the 27th ESA (LIPIcs), Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.), Vol. 144. 23:1--23:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.23"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144596297514"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1990240302451"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251244"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90053-K"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.6.791"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 25th ESA (LIPIcs)","volume":"87","author":"Cygan Marek","year":"2017","unstructured":"Marek Cygan , Lukasz Kowalik , and Arkadiusz Socala . 2017 . Improving TSP tours using dynamic programming over tree decompositions . In Proceedings of the 25th ESA (LIPIcs) , Vol. 87 . 30:1--30:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.30 10.4230\/LIPIcs.ESA.2017.30 Marek Cygan, Lukasz Kowalik, and Arkadiusz Socala. 2017. Improving TSP tours using dynamic programming over tree decompositions. In Proceedings of the 25th ESA (LIPIcs), Vol. 87. 30:1--30:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.30"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341730"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9801-4"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/203612.203628"},{"key":"e_1_2_1_27_1","unstructured":"P. C. Gilmore E. L. Lawler and D. B. Shmoys. 1985. Well-solved special cases. In The Traveling Salesman Problem E. L. Lawler J. K. Lenstra A. H. G. Rinnooy Kan and D. B. Shmoys (Eds.). Wiley New York 87--143.  P. C. Gilmore E. L. Lawler and D. B. Shmoys. 1985. Well-solved special cases. In The Traveling Salesman Problem E. L. Lawler J. K. Lenstra A. H. G. Rinnooy Kan and D. B. Shmoys (Eds.). Wiley New York 87--143."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00247211"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9685-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"volume-title":"Local Search in Combinatorial Optimization","author":"Johnson D. S.","key":"e_1_2_1_31_1","unstructured":"D. S. Johnson and L. A. McGeoch . 1997. The traveling salesman problem: A case study in local optimization . In Local Search in Combinatorial Optimization , E. Aarts and J. K. Lenstra (Eds.). Wiley , Chichester , 215--310. D. S. Johnson and L. A. McGeoch. 1997. The traveling salesman problem: A case study in local optimization. In Local Search in Combinatorial Optimization, E. Aarts and J. K. Lenstra (Eds.). Wiley, Chichester, 215--310."},{"volume-title":"The Traveling Salesman Problem and its Variations","author":"Johnson D. S.","key":"e_1_2_1_32_1","unstructured":"D. S. Johnson and L. A. McGeoch . 2002. Experimental analysis of heuristics for the STSP . In The Traveling Salesman Problem and its Variations , G. Gutin and A. Punnen (Eds.). Kluwer Academic Publishers , Dordrecht , 369--443. D. S. Johnson and L. A. McGeoch. 2002. Experimental analysis of heuristics for the STSP. In The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen (Eds.). Kluwer Academic Publishers, Dordrecht, 369--443."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017460.1017461"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_70"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1965.tb04146.x"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.02.008"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573972"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2007.7"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2716282.2716287"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.27"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313831.3376151"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3839"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220041"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90085-5"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414845","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3414845","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:45Z","timestamp":1750202625000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414845"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,31]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1,31]]}},"alternative-id":["10.1145\/3414845"],"URL":"https:\/\/doi.org\/10.1145\/3414845","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,12,31]]},"assertion":[{"value":"2020-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}