An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem

Given an arc-weighted directed graph G = (V, A, scrL) and a pair of vertices s, t, we seek to find an s-t walk of minimum length that visits all the vertices in V. If scrL satisfies the asymmetric triangle inequality, the problem is equivalent to that of finding an s-t path of minimum length that visits all the vertices. We refer to this problem as ATSPP. When s = t this is the well known asymmetric traveling salesman tour problem (ASTP). Although an O(log n) approximation ratio has long been known for ATSP, the best known ratio for ATSPP is O(sqrt n). Here we present a polynomial time algorithm with an approximation ratio of O(log n). Our algorithm generalizes to the problem of finding a minimum length path or cycle that needs to visit some subset of vertices v sub 1, v sub 2,...v sub k in the given order.