FPT Approximation Algorithms for TSP on Non-Metric Graphs

Jingyang Zhao; Zimo Sheng; Mingyu Xiao

AAAI 2026technical0 citations

FPT Approximation Algorithms for TSP on Non-Metric Graphs

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) 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

BibTeX

@inproceedings{aaai2026_fptapproximation,
  title = {FPT Approximation Algorithms for TSP on Non-Metric Graphs},
  author = {Jingyang Zhao and Zimo Sheng and Mingyu Xiao},
  booktitle = {AAAI 2026},
  year = {2026}
}