1.6-Approximation Algorithm for Generalized Traveling Salesman Path Problem
摘要
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.