A note on the approximation of the Asymmetric Traveling Salesman Problem

We show that some asymmetric traveling salesman problem (ATSP) instances are approximable within bounds equal to 3 and 9/5, when they satisfy sufficient conditions more restrictive than the triangle inequality, very simple to test and nicely structured: they only depend on a measure of satisfaction of the triangle inequality and a measure of the graph asymmetry. We discuss the applicability of such conditions and we present two preprocessing linear programs to reformulate ATSP instances into equivalent ones achieving data-dependent bounds by the same approximation algorithms.