The traveling salesman problem and its related variants are fundamental research topics in the fields of graph theory and combinatorial optimization. In this paper, we consider a variant of traveling salesman problem, called generalized traveling salesman path problem, and propose a 1.6-approximation algorithm. Compared to the previous result, the algorithm designed in this paper performs additional edge deletion and addition operations before searching for wrong-degree vertices set. This is the key factor that enables our work to improve the approximation ratio.

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

1.6-Approximation Algorithm for Generalized Traveling Salesman Path Problem

  • Rui Li,
  • Xianhao Meng,
  • Jian Sun,
  • Yijing Wang

摘要

The traveling salesman problem and its related variants are fundamental research topics in the fields of graph theory and combinatorial optimization. In this paper, we consider a variant of traveling salesman problem, called generalized traveling salesman path problem, and propose a 1.6-approximation algorithm. Compared to the previous result, the algorithm designed in this paper performs additional edge deletion and addition operations before searching for wrong-degree vertices set. This is the key factor that enables our work to improve the approximation ratio.