Improved FPT Approximation for Non-metric TSP
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916320090521600 |
|---|---|
| author | Bampis, Evripidis Escoffier, Bruno Xefteris, Michalis |
| author_facet | Bampis, Evripidis Escoffier, Bruno Xefteris, Michalis |
| contents | In the Traveling Salesperson Problem (TSP) we are given a list of locations and the distances between each pair of them. The goal is to find the shortest possible tour that visits each location exactly once and returns to the starting location. Inspired by the fact that general TSP cannot be approximated in polynomial time within any constant factor, while metric TSP admits a (slightly better than) $1.5$-approximation in polynomial time, Zhou, Li and Guo [Zhou et al., ISAAC '22] introduced a parameter that measures the distance of a given TSP instance from the metric case. They gave an FPT $3$-approximation algorithm parameterized by $k$, where $k$ is the number of triangles in which the edge costs violate the triangle inequality. In this paper, we design a $2.5$-approximation algorithm that runs in FPT time, improving the result of [Zhou et al., ISAAC '22]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_08392 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved FPT Approximation for Non-metric TSP Bampis, Evripidis Escoffier, Bruno Xefteris, Michalis Data Structures and Algorithms In the Traveling Salesperson Problem (TSP) we are given a list of locations and the distances between each pair of them. The goal is to find the shortest possible tour that visits each location exactly once and returns to the starting location. Inspired by the fact that general TSP cannot be approximated in polynomial time within any constant factor, while metric TSP admits a (slightly better than) $1.5$-approximation in polynomial time, Zhou, Li and Guo [Zhou et al., ISAAC '22] introduced a parameter that measures the distance of a given TSP instance from the metric case. They gave an FPT $3$-approximation algorithm parameterized by $k$, where $k$ is the number of triangles in which the edge costs violate the triangle inequality. In this paper, we design a $2.5$-approximation algorithm that runs in FPT time, improving the result of [Zhou et al., ISAAC '22]. |
| title | Improved FPT Approximation for Non-metric TSP |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.08392 |