{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T05:15:27Z","timestamp":1780636527837,"version":"3.54.1"},"reference-count":28,"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"}],"funder":[{"name":"NWO in the Gravitation Programme Networks","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}]}],"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>We consider the online traveling salesperson problem (TSP), where requests appear online over time on the real line and need to be visited by a server initially located at the origin. We distinguish between closed and open online TSP, depending on whether the server eventually needs to return to the origin or not. While online TSP on the line is a very natural online problem that was introduced more than two decades ago, no tight competitive analysis was known to date. We settle this problem by providing tight bounds on the competitive ratios for both the closed and the open variant of the problem. In particular, for closed online TSP, we provide a 1.64-competitive algorithm, thus matching a known lower bound. For open online TSP, we give a new upper bound as well as a matching lower bound that establish the remarkable competitive ratio of 2.04.<\/jats:p>\n          <jats:p>\n            Additionally, we consider the online D\n            <jats:sc>IAL<\/jats:sc>\n            -A-R\n            <jats:sc>IDE<\/jats:sc>\n            problem on the line, where each request needs to be transported to a specified destination. We provide an improved non-preemptive lower bound of 1.75 for this setting, as well as an improved preemptive algorithm with competitive ratio\u00a02.41.\n          <\/jats:p>\n          <jats:p>\n            Finally, we generalize known and give new complexity results for the underlying offline problems. In particular, we give an algorithm with running time\u00a0\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) for closed offline TSP on the line with release dates and show that both variants of offline D\n            <jats:sc>IAL<\/jats:sc>\n            -A-R\n            <jats:sc>IDE<\/jats:sc>\n            on the line are NP-hard for any capacity\u00a0\n            <jats:italic>c<\/jats:italic>\n            \u2265 2 of the server.\n          <\/jats:p>","DOI":"10.1145\/3422362","type":"journal-article","created":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T18:48:01Z","timestamp":1609440481000},"page":"1-58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Tight Bounds for Online TSP on the Line"],"prefix":"10.1145","volume":"17","author":[{"given":"Antje","family":"Bjelde","sequence":"first","affiliation":[{"name":"Humboldt-Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Hackfeld","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yann","family":"Disser","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Dolivostra, Darmstadt, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christoph","family":"Hansknecht","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Braunschweig, Braunschweig, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maarten","family":"Lipmann","sequence":"additional","affiliation":[{"name":"Amsterdam, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julie","family":"Mei\u00dfner","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Miriam","family":"Schl\u00d6ter","sequence":"additional","affiliation":[{"name":"Eidgen\u00f6ssische Technische Hochschule Z\u00fcrich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kevin","family":"Schewior","sequence":"additional","affiliation":[{"name":"Universit\u00e4t zu K\u00f6ln, Cologne, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[{"name":"Centrum Wiskunde 8 Informatica and Vrije Universiteit and INRIA-Erable"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,12,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1986200100791"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Conference of Operations Research (OR\u201998)","author":"Ascheuer Norbert","year":"1998","unstructured":"Norbert Ascheuer , Martin Gr\u00f6tschel , Sven Oliver Krumke , and J\u00f6rg Rambau . 1998 . Combinatorial on-line optimization . In Proceedings of the International Conference of Operations Research (OR\u201998) . 21--37. Norbert Ascheuer, Martin Gr\u00f6tschel, Sven Oliver Krumke, and J\u00f6rg Rambau. 1998. Combinatorial on-line optimization. In Proceedings of the International Conference of Operations Research (OR\u201998). 21--37."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/646514.695679"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217053"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645897.672112"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/645930.672867"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010071"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039749"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.13.2.138.10517"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796446"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1030.0052"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00261-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1029"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.5.655"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00074-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21799"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1070.0450"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Combinatorial Algorithms, Courant Computer Science Symposium. 17--29","author":"Karp Richard M.","year":"1972","unstructured":"Richard M. Karp . 1972 . Two combinatorial problems associated with external sorting . In Proceedings of the Combinatorial Algorithms, Courant Computer Science Symposium. 17--29 . Richard M. Karp. 1972. Two combinatorial problems associated with external sorting. In Proceedings of the Combinatorial Algorithms, Courant Computer Science Symposium. 17--29."},{"key":"e_1_2_1_20_1","unstructured":"Sven O. Krumke. 2001. Online Optimization Competitive Analysis and Beyond. Habilitation thesis.  Sven O. Krumke. 2001. Online Optimization Competitive Analysis and Beyond. Habilitation thesis."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2780705.2781196"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/646689.703116"},{"key":"e_1_2_1_23_1","volume-title":"Alexander H. G. Rinnooy Kan, and David B. Shmoys (Eds.).","author":"Lawler Eugene L.","year":"1985","unstructured":"Eugene L. Lawler , Jan Karel Lenstra , Alexander H. G. Rinnooy Kan, and David B. Shmoys (Eds.). 1985 . The Traveling Salesman Problem; A Guided Tour of Combinatorial Optimization. Wiley , Chichester. Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, and David B. Shmoys (Eds.). 1985. The Traveling Salesman Problem; A Guided Tour of Combinatorial Optimization. Wiley, Chichester."},{"key":"e_1_2_1_24_1","unstructured":"Maarten Lipmann. 2003. On-Line Routing. Ph.D. Dissertation. Technical University Eindhoven.  Maarten Lipmann. 2003. On-Line Routing. Ph.D. Dissertation. Technical University Eindhoven."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"e_1_2_1_26_1","first-page":"212","article-title":"Routing and scheduling on a shoreline with release times. Manage","volume":"36","author":"Psaraftis Harilaos N.","year":"1990","unstructured":"Harilaos N. Psaraftis , Marius M. Solomon , Thomas L. Magnanti , and Tai-Up Kim . 1990 . Routing and scheduling on a shoreline with release times. Manage . Sci. 36 , 2 (1990), 212 -- 223 . Harilaos N. Psaraftis, Marius M. Solomon, Thomas L. Magnanti, and Tai-Up Kim. 1990. Routing and scheduling on a shoreline with release times. Manage. Sci. 36, 2 (1990), 212--223.","journal-title":"Sci."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645591.660083"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220305"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422362","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3422362","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:21Z","timestamp":1750197801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422362"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,31]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1,31]]}},"alternative-id":["10.1145\/3422362"],"URL":"https:\/\/doi.org\/10.1145\/3422362","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,31]]},"assertion":[{"value":"2018-07-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"}}]}}