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

摘要

Given an arc-weighted directed graph G = (V, A, l) 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 l 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 (ATSP). Although an O(log n) approximation ratio has long been known for ATSP, the best known ratio for ATSPPis O(n~(1/2)). In this paper we present a polynomial time algorithm for ATSPPthat has approximation ratio of O(log n). The algorithm generalizes to the problem of finding a minimum length path or cycle that is required to visit a subset of vertices in a given order.