Approximation Ineffectiveness of a Tour-Untangling Heuristic

Bodo Manthey; Jesse van Rhijn

Approximation Ineffectiveness of a Tour-Untangling Heuristic

Research output: Working paper › Preprint › Academic

36 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 language	English
Publisher	ArXiv.org
Number of pages	13
Publication status	Accepted/In press - 22 Aug 2023

Access to Document

2302.11264Final published version, 496 KBLicence: CC BY

https://arxiv.org/abs/2302.11264Licence: CC BY

1 Conference contribution

Approximation Ineffectiveness of a Tour-Untangling Heuristic
Manthey, B. & van Rhijn, J., 22 Dec 2023, Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings. Byrka, J. & Wiese, A. (eds.). Cham: Springer, p. 1-13 13 p. (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

Open Access
File
44 Downloads (Pure)

Cite this

@techreport{008f010ece394bf3a5f45b80bb1fe268,

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

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.",

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

year = "2023",

month = aug,

day = "22",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Approximation Ineffectiveness of a Tour-Untangling Heuristic

AU - Manthey, Bodo

AU - van Rhijn, Jesse

PY - 2023/8/22

Y1 - 2023/8/22

N2 - 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.

AB - 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.

M3 - Preprint

BT - Approximation Ineffectiveness of a Tour-Untangling Heuristic

PB - ArXiv.org

ER -

Approximation Ineffectiveness of a Tour-Untangling Heuristic

Abstract

Access to Document

Fingerprint

Research output

Approximation Ineffectiveness of a Tour-Untangling Heuristic

Cite this