An LP-based 3/2-approximation algorithm for the graphic s-t path TSP

2013/04/26 by Zhihan Gao, Gao, Zhihan
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Vehicle Routing Optimization Methods #cs.DS

paper · pdf · doi:10.48550/arxiv.1304.7055

arxiv created 2013/04/26 · openalex publication_date 2013/04/26 · arxiv updated 2013/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We design a new LP-based algorithm for the graphic s-t path Traveling Salesman Problem (TSP), which achieves the best approximation factor of 1.5. The algorithm is based on the idea of narrow cuts due to An, Kleinberg, and Shmoys. It partly answers an open question of Sebő.

Related

• LP-Based Approximation Algorithms for Traveling Salesman Path Problems
• Beating the integrality ratio for s-t-tours in graphs
• Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
• Reducing Path TSP to TSP
• 13/9-approximation for Graphic TSP