Approximation Ineffectiveness of a Tour-Untangling Heuristic

Bodo Manthey, Jesse van Rhijn*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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 languageEnglish
Title of host publicationApproximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings
EditorsJarosław Byrka, Andreas Wiese
Place of PublicationCham
Number of pages13
ISBN (Electronic) 978-3-031-49815-2
ISBN (Print)978-3-031-49814-5
Publication statusE-pub ahead of print/First online - 22 Dec 2023
Event21st International Workshop on Approximation and Online Algorithms, WAOA 2023 - Amsterdam Science Park, Amsterdam, Netherlands
Duration: 7 Sept 20238 Sept 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14297 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International Workshop on Approximation and Online Algorithms, WAOA 2023


  • 2024 OA procedure
  • Probabilistic analysis
  • Travelling salesperson problem
  • Local search


Dive into the research topics of 'Approximation Ineffectiveness of a Tour-Untangling Heuristic'. Together they form a unique fingerprint.

Cite this