Approximation Ineffectiveness of a Tour-Untangling Heuristic

MaRDI QIDQ6427259zbMATH OpenFDO

Authors Bodo Manthey, Jesse van Rhijn

Publication date 22 February 2023

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(sqrtn)$ 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.

This page was built for publication: Approximation Ineffectiveness of a Tour-Untangling Heuristic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6427259)