Approximation Ineffectiveness of a Tour-Untangling Heuristic

Bodo Manthey; Jesse van Rhijn

doi:10.1007/978-3-031-49815-2_1

Approximation Ineffectiveness of a Tour-Untangling Heuristic

Bodo Manthey, Jesse van Rhijn^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

46 Downloads (Pure)

Abstract

We analyze a tour-uncrossing heuristic for the Euclidean Travelling Salesperson Problem, showing that its worst-case approximation ratio is and its average-case approximation ratio is in expectation. We furthermore evaluate the approximation performance of this heuristic numerically on average-case instances, and find that it performs far better than the average-case lower bound suggests. This indicates a shortcoming in the approach we use for our analysis, which is a rather common method in the analysis of local search heuristics.

Original language	English
Title of host publication	Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings
Editors	Jarosław Byrka, Andreas Wiese
Place of Publication	Cham
Publisher	Springer
Pages	1-13
Number of pages	13
ISBN (Electronic)	978-3-031-49815-2
ISBN (Print)	978-3-031-49814-5
DOIs	https://doi.org/10.1007/978-3-031-49815-2_1
Publication status	Published - 22 Dec 2023
Event	21st International Workshop on Approximation and Online Algorithms, WAOA 2023 - Amsterdam Science Park, Amsterdam, Netherlands Duration: 7 Sept 2023 → 8 Sept 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	14297 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Workshop on Approximation and Online Algorithms, WAOA 2023
Country/Territory	Netherlands
City	Amsterdam
Period	7/09/23 → 8/09/23

Keywords

2024 OA procedure
Probabilistic analysis
Travelling salesperson problem
Local search

Access to Document

10.1007/978-3-031-49815-2_1

978-3-031-49815-2_1Final published version, 386 KBLicence: Taverne

Cite this

Manthey, B., & van Rhijn, J. (2023). Approximation Ineffectiveness of a Tour-Untangling Heuristic. In J. Byrka, & A. Wiese (Eds.), Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings (pp. 1-13). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14297 LNCS). Springer. https://doi.org/10.1007/978-3-031-49815-2_1

Manthey, Bodo ; van Rhijn, Jesse. / Approximation Ineffectiveness of a Tour-Untangling Heuristic. Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings. editor / Jarosław Byrka ; Andreas Wiese. Cham : Springer, 2023. pp. 1-13 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{05b4a3b721234111aeb350f9b5915987,

title = "Approximation Ineffectiveness of a Tour-Untangling Heuristic",

abstract = "We analyze a tour-uncrossing heuristic for the Euclidean Travelling Salesperson Problem, showing that its worst-case approximation ratio is and its average-case approximation ratio is in expectation. We furthermore evaluate the approximation performance of this heuristic numerically on average-case instances, and find that it performs far better than the average-case lower bound suggests. This indicates a shortcoming in the approach we use for our analysis, which is a rather common method in the analysis of local search heuristics.",

keywords = "2024 OA procedure, Probabilistic analysis, Travelling salesperson problem, Local search",

author = "Bodo Manthey and {van Rhijn}, Jesse",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 21st International Workshop on Approximation and Online Algorithms, WAOA 2023 ; Conference date: 07-09-2023 Through 08-09-2023",

year = "2023",

month = dec,

day = "22",

doi = "10.1007/978-3-031-49815-2_1",

language = "English",

isbn = "978-3-031-49814-5",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "1--13",

editor = "Jaros{\l}aw Byrka and Andreas Wiese",

booktitle = "Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings",

address = "Germany",

}

Manthey, B & van Rhijn, J 2023, Approximation Ineffectiveness of a Tour-Untangling Heuristic. in J Byrka & A Wiese (eds), Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14297 LNCS, Springer, Cham, pp. 1-13, 21st International Workshop on Approximation and Online Algorithms, WAOA 2023, Amsterdam, Netherlands, 7/09/23. https://doi.org/10.1007/978-3-031-49815-2_1

Approximation Ineffectiveness of a Tour-Untangling Heuristic. / Manthey, Bodo; van Rhijn, Jesse.
Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings. ed. / Jarosław Byrka; Andreas Wiese. Cham: Springer, 2023. p. 1-13 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14297 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximation Ineffectiveness of a Tour-Untangling Heuristic

AU - Manthey, Bodo

AU - van Rhijn, Jesse

PY - 2023/12/22

Y1 - 2023/12/22

N2 - We analyze a tour-uncrossing heuristic for the Euclidean Travelling Salesperson Problem, showing that its worst-case approximation ratio is and its average-case approximation ratio is in expectation. We furthermore evaluate the approximation performance of this heuristic numerically on average-case instances, and find that it performs far better than the average-case lower bound suggests. This indicates a shortcoming in the approach we use for our analysis, which is a rather common method in the analysis of local search heuristics.

AB - We analyze a tour-uncrossing heuristic for the Euclidean Travelling Salesperson Problem, showing that its worst-case approximation ratio is and its average-case approximation ratio is in expectation. We furthermore evaluate the approximation performance of this heuristic numerically on average-case instances, and find that it performs far better than the average-case lower bound suggests. This indicates a shortcoming in the approach we use for our analysis, which is a rather common method in the analysis of local search heuristics.

KW - 2024 OA procedure

KW - Probabilistic analysis

KW - Travelling salesperson problem

KW - Local search

UR - http://www.scopus.com/inward/record.url?scp=85180751379&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-49815-2_1

DO - 10.1007/978-3-031-49815-2_1

M3 - Conference contribution

AN - SCOPUS:85180751379

SN - 978-3-031-49814-5

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 13

BT - Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings

A2 - Byrka, Jarosław

A2 - Wiese, Andreas

PB - Springer

CY - Cham

T2 - 21st International Workshop on Approximation and Online Algorithms, WAOA 2023

Y2 - 7 September 2023 through 8 September 2023

ER -

Manthey B, van Rhijn J. Approximation Ineffectiveness of a Tour-Untangling Heuristic. In Byrka J, Wiese A, editors, Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings. Cham: Springer. 2023. p. 1-13. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-49815-2_1

Approximation Ineffectiveness of a Tour-Untangling Heuristic

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Approximation Ineffectiveness of a Tour-Untangling Heuristic

Cite this