An Improved Integrality Gap for Asymmetric TSP Paths
An Improved Integrality Gap for Asymmetric TSP Paths
The asymmetric traveling salesperson path problem (ATSPP) is one where, given an asymmetric metric space (V, d) with specified vertices s and t, the goal is to find an s-t path of minimum length that passes through all the vertices in V. This problem is closely related to the asymmetric …