Bjelde, Antje, Hackfeld, Jan, Disser, Yann, Hansknecht, Christoph, Lipmann, Maarten, Meissner, Julie, Schloter, Miriam, Schewior, Kevin ORCID: 0000-0003-2236-0210 and Stougie, Leen (2021). Tight Bounds for Online TSP on the Line. ACM Trans. Algorithms, 17 (1). NEW YORK: ASSOC COMPUTING MACHINERY. ISSN 1549-6333

Full text not available from this repository.

Abstract

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. Additionally, we consider the online DIAL-A-RIDE 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 2.41. Finally, we generalize known and give new complexity results for the underlying offline problems. In particular, we give an algorithm with running time O(n(2)) for closed offline TSP on the line with release dates and show that both variants of offline DIAL-A-RIDE on the line are NP-hard for any capacity c >= 2 of the server.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Bjelde, AntjeUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Hackfeld, JanUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Disser, YannUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Hansknecht, ChristophUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Lipmann, MaartenUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Meissner, JulieUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schloter, MiriamUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schewior, KevinUNSPECIFIEDorcid.org/0000-0003-2236-0210UNSPECIFIED
Stougie, LeenUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-597409
DOI: 10.1145/3422362
Journal or Publication Title: ACM Trans. Algorithms
Volume: 17
Number: 1
Date: 2021
Publisher: ASSOC COMPUTING MACHINERY
Place of Publication: NEW YORK
ISSN: 1549-6333
Language: English
Faculty: Unspecified
Divisions: Unspecified
Subjects: no entry
Uncontrolled Keywords:
KeywordsLanguage
TRAVELING SALESMAN; COMPETITIVE ALGORITHMS; COMPLEXITY; TIMEMultiple languages
Computer Science, Theory & Methods; Mathematics, AppliedMultiple languages
URI: http://kups.ub.uni-koeln.de/id/eprint/59740

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item