Asymmetric Traveling Salesman Path and Directed Latency Problems
Asymmetric Traveling Salesman Path and Directed Latency Problems
We study integrality gaps and approximability of three closely related problems on directed graphs with edge lengths that satisfy the triangle inequality. Given two specified vertices $s$ and $t$, two of these problems ask to find an $s$-$t$ path in the graph visiting all other vertices. In the asymmetric traveling …