We present a deterministic (1+√5)/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost between n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints. The present result surpasses the 20-year-old barrier of 5/3 originating from Hoogeveen's analysis of the natural path-variant of Christofides' algorithm. The present techniques can be applied to other optimization problems as well: these applications include the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.
H.-C. An, R. Kleinberg. A diameter-revealing proof of the Bondy-Lovász Lemma. Available online at http://arxiv.org/abs/1111.6561, 2011.We present a strengthened version of a lemma due to Bondy and Lovász. This lemma establishes the connectivity of a certain graph whose nodes correspond to the spanning trees of a 2-vertex-connected graph, and implies the k=2 case of the Győri-Lovász Theorem on partitioning of k-vertex-connected graphs. Our strengthened version constructively proves an asymptotically tight O(|V|2) bound on the worst-case diameter of this graph of spanning trees.
H.-C. An, R. D. Kleinberg, and D. B. Shmoys. Approximation algorithms for the bottleneck asymmetric traveling salesman problem. In APPROX 2010: Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 1-11, 2010.We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O(log n / log log n) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on the result of Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi to obtain this guarantee.
H.-C. An, A polynomial-time algorithm to find optimal path decompositions of trees. Journal of Korea Information Science Society, 34(5):195-201, 2007.We present an O(|V|2)-time algorithm to find a minimum terminal path decomposition of a tree. A minimum terminal path decomposition is a partition of a tree into edge-disjoint terminal-to-terminal paths that minimizes the weight of the longest path. For the case where the input tree is unit-weighted, we give an O(|V| log2 |V|)-time algorithm.