In this paper, we study the Traveling Salesman Problem (TSP), where given a weighted undirected complete graph, the goal is to find a minimum-weight cycle visiting every vertex exactly once. Motivated by different polynomial-time approximability of TSP, that is, TSP on general graphs cannot be approximated within any factor, while on metric graphs, where the edge weights satisfy the triangle inequality, admits a \((1.5-\varepsilon )\) -approximation, Zhou et al. [ISAAC ’22] introduced a parameter \(\beta \) to measure the distance from a given instance to a metric graph and proposed a \((6\beta +9)\) -approximation algorithm for TSP running in \(\beta ^{O(\beta )} \cdot n^3\) time, where \(\beta \) is the number of vertices, whose removal from a given graph results in a metric graph. Bampis et al. posed it as an open question, whether there exists an FPT constant approximation algorithm for TSP, parameterized by \(\beta \) . In this paper, we answer this open question affirmatively by providing an 11-approximation algorithm for TSP running in \(\beta ^{O(\beta )} \cdot n^3\) time, which greatly improves the result by Zhou et al.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An FPT Factor-11 Approximation Algorithm for TSP

  • Jianqi Zhou,
  • Zhongyi Zhang,
  • Jiong Guo

摘要

In this paper, we study the Traveling Salesman Problem (TSP), where given a weighted undirected complete graph, the goal is to find a minimum-weight cycle visiting every vertex exactly once. Motivated by different polynomial-time approximability of TSP, that is, TSP on general graphs cannot be approximated within any factor, while on metric graphs, where the edge weights satisfy the triangle inequality, admits a \((1.5-\varepsilon )\) -approximation, Zhou et al. [ISAAC ’22] introduced a parameter \(\beta \) to measure the distance from a given instance to a metric graph and proposed a \((6\beta +9)\) -approximation algorithm for TSP running in \(\beta ^{O(\beta )} \cdot n^3\) time, where \(\beta \) is the number of vertices, whose removal from a given graph results in a metric graph. Bampis et al. posed it as an open question, whether there exists an FPT constant approximation algorithm for TSP, parameterized by \(\beta \) . In this paper, we answer this open question affirmatively by providing an 11-approximation algorithm for TSP running in \(\beta ^{O(\beta )} \cdot n^3\) time, which greatly improves the result by Zhou et al.