Approximation Ineffectiveness of a Tour-Untangling Heuristic

Autor:	Manthey, Bodo, van Rhijn, Jesse
Rok vydání:	2023
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics Mathematics - Probability
Druh dokumentu:	Working Paper
Popis:	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. Comment: Accepted for presentation at WAOA 2023
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2302.11264 Zobrazit plný text záznamu View this record from Arxiv