A better-than-1.6-approximation for prize-collecting TSP

Area of Science:

• Operations Research
• Computer Science
• Combinatorial Optimization

Background:

• The Prize-Collecting Traveling Salesperson Problem (TSP) involves minimizing tour length plus penalties for unvisited vertices.
• Existing approximation algorithms for Prize-Collecting TSP have limitations in solution quality.

Purpose of the Study:

• To develop a more effective approximation algorithm for the Prize-Collecting TSP.
• To improve the approximation ratio compared to existing methods.

Main Methods:

• The study utilizes a polynomial-time approximation algorithm based on linear programming relaxation.
• The approach involves decomposing solutions into rooted trees, followed by pruning and parity correction.
• The algorithm's performance is analyzed using mathematical bounds, including the golden ratio.

Main Results:

• The proposed algorithm achieves an approximation guarantee of approximately 1.599 for Prize-Collecting TSP, surpassing the previous 1.774 ratio.
• For the Prize-Collecting Stroll (path version), an improved approximation guarantee of 1.6662 is demonstrated, outperforming the prior 1.926 ratio.

Conclusions:

• The new algorithm offers a significant improvement in approximation guarantees for Prize-Collecting TSP and its path variant.
• This research advances the field of combinatorial optimization by providing more efficient solutions for complex routing problems.