Tight Bounds for Online TSP on the Line

Antje Bjelde; Jan Hackfeld; Yann Disser; Christoph Hansknecht; Maarten Lipmann; Julie Meißner; Miriam Schlöter; Kevin Schewior; Leen Stougie

doi:10.1145/3422362

Tight Bounds for Online TSP on the Line

Antje Bjelde
, Jan Hackfeld
, Yann Disser
, Christoph Hansknecht
, Maarten Lipmann
, Julie Meißner
, Miriam Schlöter
, Kevin Schewior
, Leen Stougie

Research output: Contribution to Journal › Article › Academic › peer-review

115 Downloads (Pure)

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) 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.

Original language	English
Article number	3
Pages (from-to)	1-58
Number of pages	58
Journal	ACM Transactions on Algorithms
Volume	17
Issue number	1
Early online date	31 Dec 2020
DOIs	https://doi.org/10.1145/3422362
Publication status	Published - Jan 2021

Bibliographical note

Funding Information:
A preliminary version of this article appeared in Reference [8]. Leen Stougie was supported by the NWO in the Gravitation Programme Networks, Grant No. 024.002.003. Authors’ addresses: A. Bjelde and J. Hackfeld, Humboldt-Universität Berlin, Berlin, Germany; email: {antje.bjelde, jan.hackfeld}@hu-berlin.de; Y. Disser, Department of Mathematics, Technische Universität Darmstadt, Dolivostraße 15, 64293 Darmstadt, Germany; email: disser@mathematik. tu-darmstadt.de; C. Hansknecht, Technische Universität Braunschweig, Braunschweig, Germany; email: [email protected]; M. Lipmann, Amsterdam, Amsterdam, The Netherlands; email: [email protected]; J. Meißner, Technische Universität Berlin, Berlin, Germany; email: [email protected]; M. Schlöter, Eidgenössische Technische Hochschule Zürich, Zurich, Switzerland; email: [email protected]; K. Schewior, Universität zu Köln, Cologne, Germany; email: [email protected]; L. Stougie, Centrum Wiskunde & Informatica, Amsterdam, The Netherlands; Vrije Universiteit; and INRIA-Erable; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1549-6325/2020/12-ART3 $15.00 https://doi.org/10.1145/3422362

Publisher Copyright:
© 2020 ACM.

Funding

A preliminary version of this article appeared in Reference [8]. Leen Stougie was supported by the NWO in the Gravitation Programme Networks, Grant No. 024.002.003. Authors’ addresses: A. Bjelde and J. Hackfeld, Humboldt-Universität Berlin, Berlin, Germany; email: {antje.bjelde, jan.hackfeld}@hu-berlin.de; Y. Disser, Department of Mathematics, Technische Universität Darmstadt, Dolivostraße 15, 64293 Darmstadt, Germany; email: disser@mathematik. tu-darmstadt.de; C. Hansknecht, Technische Universität Braunschweig, Braunschweig, Germany; email: [email protected]; M. Lipmann, Amsterdam, Amsterdam, The Netherlands; email: [email protected]; J. Meißner, Technische Universität Berlin, Berlin, Germany; email: [email protected]; M. Schlöter, Eidgenössische Technische Hochschule Zürich, Zurich, Switzerland; email: [email protected]; K. Schewior, Universität zu Köln, Cologne, Germany; email: [email protected]; L. Stougie, Centrum Wiskunde & Informatica, Amsterdam, The Netherlands; Vrije Universiteit; and INRIA-Erable; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1549-6325/2020/12-ART3 $15.00 https://doi.org/10.1145/3422362

Keywords

approximation algorithms
competitive analysis
computational complexity
online algorithms
TSP

Access to Document

10.1145/3422362

Tight Bounds for Online TSP on the LineFinal published version, 800 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

@article{be8fea1c653149bdbad603de50570c6a,

title = "Tight Bounds for Online TSP on the Line",

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) 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.",

keywords = "approximation algorithms, competitive analysis, computational complexity, online algorithms, TSP",

author = "Antje Bjelde and Jan Hackfeld and Yann Disser and Christoph Hansknecht and Maarten Lipmann and Julie Mei{\ss}ner and Miriam Schl{\"o}ter and Kevin Schewior and Leen Stougie",

note = "Funding Information: A preliminary version of this article appeared in Reference [8]. Leen Stougie was supported by the NWO in the Gravitation Programme Networks, Grant No. 024.002.003. Authors{\textquoteright} addresses: A. Bjelde and J. Hackfeld, Humboldt-Universit{\"a}t Berlin, Berlin, Germany; email: \{antje.bjelde, jan.hackfeld\}@hu-berlin.de; Y. Disser, Department of Mathematics, Technische Universit{\"a}t Darmstadt, Dolivostra{\ss}e 15, 64293 Darmstadt, Germany; email: disser@mathematik. tu-darmstadt.de; C. Hansknecht, Technische Universit{\"a}t Braunschweig, Braunschweig, Germany; email: [email protected]; M. Lipmann, Amsterdam, Amsterdam, The Netherlands; email: [email protected]; J. Mei{\ss}ner, Technische Universit{\"a}t Berlin, Berlin, Germany; email: [email protected]; M. Schl{\"o}ter, Eidgen{\"o}ssische Technische Hochschule Z{\"u}rich, Zurich, Switzerland; email: [email protected]; K. Schewior, Universit{\"a}t zu K{\"o}ln, Cologne, Germany; email: [email protected]; L. Stougie, Centrum Wiskunde \& Informatica, Amsterdam, The Netherlands; Vrije Universiteit; and INRIA-Erable; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. {\textcopyright} 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1549-6325/2020/12-ART3 \$15.00 https://doi.org/10.1145/3422362 Publisher Copyright: {\textcopyright} 2020 ACM.",

year = "2021",

month = jan,

doi = "10.1145/3422362",

language = "English",

volume = "17",

pages = "1--58",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "1",

}

TY - JOUR

T1 - Tight Bounds for Online TSP on the Line

AU - Bjelde, Antje

AU - Hackfeld, Jan

AU - Disser, Yann

AU - Hansknecht, Christoph

AU - Lipmann, Maarten

AU - Meißner, Julie

AU - Schlöter, Miriam

AU - Schewior, Kevin

AU - Stougie, Leen

N1 - Funding Information: A preliminary version of this article appeared in Reference [8]. Leen Stougie was supported by the NWO in the Gravitation Programme Networks, Grant No. 024.002.003. Authors’ addresses: A. Bjelde and J. Hackfeld, Humboldt-Universität Berlin, Berlin, Germany; email: {antje.bjelde, jan.hackfeld}@hu-berlin.de; Y. Disser, Department of Mathematics, Technische Universität Darmstadt, Dolivostraße 15, 64293 Darmstadt, Germany; email: disser@mathematik. tu-darmstadt.de; C. Hansknecht, Technische Universität Braunschweig, Braunschweig, Germany; email: [email protected]; M. Lipmann, Amsterdam, Amsterdam, The Netherlands; email: [email protected]; J. Meißner, Technische Universität Berlin, Berlin, Germany; email: [email protected]; M. Schlöter, Eidgenössische Technische Hochschule Zürich, Zurich, Switzerland; email: [email protected]; K. Schewior, Universität zu Köln, Cologne, Germany; email: [email protected]; L. Stougie, Centrum Wiskunde & Informatica, Amsterdam, The Netherlands; Vrije Universiteit; and INRIA-Erable; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1549-6325/2020/12-ART3 $15.00 https://doi.org/10.1145/3422362 Publisher Copyright: © 2020 ACM.

PY - 2021/1

Y1 - 2021/1

N2 - 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) 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.

AB - 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) 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.

KW - approximation algorithms

KW - competitive analysis

KW - computational complexity

KW - online algorithms

KW - TSP

UR - https://www.scopus.com/pages/publications/85100290676

UR - https://www.scopus.com/pages/publications/85100290676#tab=citedBy

U2 - 10.1145/3422362

DO - 10.1145/3422362

M3 - Article

AN - SCOPUS:85100290676

SN - 1549-6325

VL - 17

SP - 1

EP - 58

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 3

ER -

Tight Bounds for Online TSP on the Line

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Tight Bounds for Online TSP on the Line

Cite this