Approximation Ineffectiveness of a Tour-Untangling Heuristic

Research output: Working paperPreprintAcademic

23 Downloads (Pure)

Abstract

We analyze a tour-uncrossing heuristic for the Travelling Salesperson Problem, showing that its worst-case approximation ratio is $\Omega(n)$ and its average-case approximation ratio is $\Omega(\sqrt{n})$ 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 approach in the analysis of local search heuristics.
Original languageEnglish
PublisherArXiv.org
Number of pages13
Publication statusAccepted/In press - 22 Aug 2023

Fingerprint

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

Cite this