2014/04/30 by Zhihan Gao, Gao, Zhihan
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Smart Parking Systems Research #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1404.7569
We study the metric s-t path Traveling Salesman Problem (TSP). [An, Kleinberg, and Shmoys, STOC 2012] improved on the long standing (5)/(3)-approximation factor and presented an algorithm that achieves an approximation factor of (1+√(5))/(2)≈1.61803. Later [Sebő, IPCO 2013] further improved the approximation factor to (8)/(5). We present a simple, self-contained analysis that unifies both results; our main contribution is a unified correction vector. We compare two different linear programming (LP) relaxations of the s-t path TSP, namely, the path version of the Held-Karp LP relaxation for TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum-cost of integral solutions of the two LPs are within a factor of (3)/(2) of each other. We prove that a half-integral solution of the stronger LP-relaxation of cost c can be rounded to an integral solution of cost at most (3)/(2)c. Additionally, we give a bad instance that presents obstructions to two obvious methods that aim for an approximation factor of (3)/(2).