On the integrality ratio for asymmetric TSP

摘要

The traveling salesman problem comes in two variants. The symmetric version (STSP) assumes that the cost c/sub ij/ of going to city i to city j is equal to c/sub ji/, while the more general asymmetric version (ATSP) does not make this assumption. In both cases, it is usually assumed that we are in the metric case, i.e., the costs satisfy the triangle inequality: c/sub ij/ + c/sub jk/ /spl ges/ c/sub ik/ for all i, j, k. In this assumption, we improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP (with triangle inequality) from 4/3 to 2.