Improved FPT Approximation Algorithms for TSP

Jingyang Zhao, Zimo Sheng, Mingyu Xiao · 2025

Read Improved FPT Approximation Algorithms for TSP by Jingyang Zhao, Zimo Sheng, Mingyu Xiao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-03642.txt.

Introduction

Jingyang Zhao, Zimo Sheng, and Mingyu Xiao improve approximation methods for the Traveling Salesman Problem on graphs that break distance rules. Their 2025 paper studies graphs where the triangle rule fails, unlike tidy metric graphs where good approximations are known. Two measures capture how far a graph strays from metric behavior.

For the first measure, the team gives a method that lands within one and a half times the best route, beating the old mark of two and a half. For the second, they improve the guarantee from eleven times optimal to three. When either measure stays fixed, the guarantees improve further. The work narrows a long-standing gap in route planning theory.

Catalog record

CREATORJingyang Zhao, Zimo Sheng, Mingyu Xiao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-03642

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Improved FPT Approximation Algorithms for TSP Jingyang Zhao, Zimo Sheng, Mingyu Xiao Abstract TSP is a classic and extensively studied problem with numerous real-world applications in artificial intelligence and operations research. It is well-known that TSP admits a constant approximation ratio on metric graphs but becomes NP-hard to approximate within any computable function f ⁡ ( n ) f(n) on general graphs. This disparity highlights a significant gap between the results on metric graphs and general graphs. Recent research has introduced some parameters to measure the “distance” of general graphs from being metric and explored FPT approximation algorithms parameterized by these parameters. Two commonly studied parameters are p p , the number of vertices in triangles violating the triangle inequality, and q q , the minimum number of vertices whose removal results in a metric graph. In this paper, we present improved FPT approximation algorithms with respect to these two parameters. For p p , we propose an FPT algorithm with a 1.5-approximation ratio, improving upon the previous ratio of 2.5. For q q , we significantly enhance the approximation ratio from 11 to 3, advancing the state of the art in both cases. 1 Introduction The Traveling Salesman Problem (TSP) is a classic optimization problem with numerous real-world applications Applegate 2006 , including logistics, genetics, manufacturing, and telecommunications. Given an edge-weighted complete graph G=(V,E,w) with n vertices in V and a non-negative weight function w:E\to\mathbb{R}_{\geq 0} on edges, the goal of TSP is to find an optimal (i.e., minimum-weight) TSP tour (i.e., Hamiltonian cycle) that visits each vertex exactly once. Due to its NP-hardness Garey and Johnson 1979 , TSP has been extensively studied in the context of approximation algorithms Saller et al. 2023 ; Traub and Vygen 2025 . For a minimization problem, an algorithm is called a \rho -approximation algorithm if, for any instance \mathcal{I} , it computes a solution with an objective value that is at most \rho times the optimal value in polynomial time poly(|\mathcal{I}|) . Here, \rho is called the approximation ratio . Moreover, with some parameter k , an algorithm is called an FPT \rho -approximation algorithm if, for any instance \mathcal{I} , it runs in \mathcal{O}(f(k))\cdot poly(|\mathcal{I}|) time with an approximation ratio of \rho , where f(k) is a computable function of k . Both FPT algorithms and FPT approximation algorithms are particularly useful in practice when the parameter k is small Cygan et al. 2015 . While TSP on general graphs is NP-hard to approximate within any computable function f(n) Sahni and Gonzalez 1976 , TSP on metric graphs (metric TSP), where the weight function satisfies the triangle inequality, admits a constant approximation ratio. Notably, Christofides Christofides 2022 and Serdyukov Serdyukov 1978 independently proposed the famous 1.5 -approximation algorithm for metric TSP. Currently, Karlin et al. Karlin et al. 2021 ; Karlin et al. 2023 have improved the approximation ratio to 1.5- 10^{-36} . Karpinski et al. Karpinski et al. 2015 showed that metric TSP is NP-hard to approximate within a ratio of 123/122 . Given the significant gap between the results on general graphs and metric graphs, many approximation algorithms have been developed for graphs that are “nearly” metric, aiming to measure the “distance” from approximability. In the literature, two main research directions are commonly explored. The first direction relaxes the condition on metric functions, where the weight function satisfies the \tau -triangle inequality : \tau\cdot(w(a,b)+w(b,c))\geq w(a,c) for all a,b,c\in V . The second direction relaxes the scope of metric functions, where the weight function partially satisfies the triangle inequality, i.e., only a subset of all triangles is required to satisfy it. For the first direction, Andreae and Bandelt Andreae and Bandelt 1995 gave a (3\tau^{2}+\tau)/2 -approximation algorithm for TSP. Bender and Chekuri Bender and Chekuri 2000 improved this ratio to 4\tau when \tau>7/3 , and Mömke Mömke 2015 further improved the ratio to 3(\tau^{2}+\tau)/4 for small values of \tau . Additional improvements Andreae 2001 ; Böckenhauer et al. 2002 can be found in a survey Klasing and Mömke 2018 . For the second direction, Mohan Mohan et al. 2017 proposed a 3.5 -approximation algorithm for TSP on graphs G=(V_{1}\cup V_{2}, E,w) , where both induced subgraphs G[V_{1}] and G[V_{2}] are required to be metric graphs. Sumita et al. Sumita et al. 2017 proposed a 3 -approximation algorithm for Subgroup Path Planning , where the vertex set V is partitioned into k disjoint groups V_{1},...,V_{k} . The goal is to find an optimal TSP tour visiting the vertices in each group V_{i} consecutively, where the weight function violates w(a,b)+w(b,c)\geq w(a,c) only if both a and c belong to the same group, while b belongs to a different group. Moreover, if it holds that |V_{i}|=2 for all i , the problem reduces to Subpath Planning Safilian et al. 2016 , which admits a 1.5 -approximation algorithm Sumita et al. 2017 . Both problems have various applications in AI, such as polishing robots and electronic printing Safilian et al. 2016 ; Sumita et al. 2017 . Subsequently, Zhou et al. Zhou et al. 2022 ; Zhou et al. 2024 introduced two natural parameters: the number of vertices p in violating triangles that do not satisfy the triangle inequality, and the minimum number of violating vertices q whose removal results in a metric graph. Note that q\leq p . Moreover, the parameter p can be computed in polynomial time, while q can be computed in \mathcal{O}(3^{q}n^{3}) time using the search-tree method Zhou et al. 2022 . For TSP parameterized by p , they proposed an FPT 3 -approximation algorithm with a running time of 2^{\mathcal{O}({p\log p})}\cdot n^{\mathcal{O}(1)} . For TSP parameterized by q , they proposed a 3 -approximation algorithm with a running time of n^{\mathcal{O}(q+1)} , and an FPT 11 -approximation algorithm with a running time of 2^{\mathcal{O}({q\log q})}\cdot n^{\mathcal{O}(1)} . Recently, Bampis et al. Bampis et al. 2024 improved the FPT approximation ratio from 3 to 2.5 for the parameter p , while maintaining the running time of 2^{\mathcal{O}({p\log p})}\cdot n^{\mathcal{O}(1)} . Our research follows this line to study FPT approximation algorithms for TSP with respect to these two parameters. 1.1 Our results In this paper, we present improved FPT approximation algorithms for TSP with respect to the parameters p and q , addressing the question raised in Bampis et al. 2024 regarding the potential for further improvement in the approximation ratio. Let \alpha denote the approximation ratio for metric TSP. Currently, the best-known value of \alpha is \alpha=1.5-10^{-36} Karlin et al. 2023 . Our results are summarized as follows. For TSP parameterized by p , we first introduce a simple (\alpha+1) -approximation algorithm with a running time of 2^{\mathcal{O}(p)}+n^{\mathcal{O}(1)} . This improves upon the previous 2.5-approximation algorithm, which has a worse running time of 2^{\mathcal{O}(p\log p)}\cdot n^{\mathcal{O}(1)} Bampis et al. 2024 . Additionally, we propose a more sophisticated 1.5 -approximation algorithm, though it comes with a running time of 2^{\mathcal{O}(p\log p)}\cdot n^{\mathcal{O}(1)} . For TSP parameterized by q , we present an FPT 3 -approximation algorithm, significantly improving upon the previous FPT 11 -approximation algorithm Zhou et al. 2024 . Both algorithms run in 2^{\mathcal{O}(q\log q)}\cdot n^{\mathcal{O}(1)} time. Our result also matches the approximation ratio of the earlier algorithm with

Read the complete text