LP-Based Approximation Algorithms for Traveling Salesman Path Problems

2011/05/12 by Hyung-Chan An, David B. Shmoys, An, Hyung-Chan +1
Computer Science · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1105.2391

This paper has been merged into 1110.4604

arxiv created 2011/10/28 · arxiv updated 2011/10/31

Abstract

This paper has been merged into 1110.4604.

Related

• An LP-based 3/2-approximation algorithm for the graphic s-t path TSP
• Reducing Path TSP to TSP
• Approximation Algorithms for the Asymmetric Traveling Salesman Problem : Describing two recent methods
• A 1.5-Approximation for Path TSP
• 13/9-approximation for Graphic TSP