2026
FPT Approximation Algorithms for TSP on Non-Metric Graphs
AAAI 2026technical
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) on genera