LP-based solution methods for the asymmetric TSP.pdfVIP

LP-based solution methods for the asymmetric TSP Vardges Melkonian Department of Mathematics, Ohio Universtiy, Athens, Ohio 45701, USA vardges@ Abstract We consider an LP relaxation for ATSP. We introduce concepts of high-value and high-flow cycles in LP basic solutions and show that the existence of this kind of cycles would lead to constant-factor approximation algorithms for ATSP. The existence of high-flow cycles is motivated by computational results and theoretical observations. (Keywords: TSP; Linear programming; Network flows; Approximation algorithm) 1. Introduction In Traveling Salesman problem (TSP), it is required to find a minimum cost Hamiltonian tour, that is, a cycle passing through each node exactly once. A nice collection of papers tracing the history and research on the problem can be found in Lawler et al.[7]. Most of the research on TSP algorithms has concentrated on the undirected version of TSP. The best approximation factor for the case when the arc costs satisfy the triangle inequality in undirected networks is 1.5 and was obtained by Christofides ([1]). Far less research is done on the version of TSP in directed graphs to which we will refer as Asymmetric TSP (ATSP). The best approximation ratio of O(log n) was achieved first by Frieze et al. [2] and later by Kleinberg and Williamson [6]. The current best approximation algorithm for ATSP is by Kaplan et al. [5] and achieves approximation ratio 0.842 log n. However the best-known lower bound on the approximation factor is only 117/116 [9]. This low lower bound and the discrepancy between the best approximation factors for symmetric and asymmetric cases give hopes that there should be an algorithm with a constant approximation factor for ATSP. In this paper we will explore one directio