Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED

Question

NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really a TSP variant, but I put it due to lack of a better definition of the problem.

This problem was originally posted on StackOverflow, but I was told that this would be a better place. I got one pointer, which converted the problem from non-metric to a metric one.

So..

Suppose I am going on a hiking trip with n points of interest. These points are all connected by hiking trails. I have a map showing all trails with their distances, giving me a directed graph.

My problem is how to approximate a tour that starts at a point A and visits all n points of interest, while ending the tour anywhere but the point where I started and I want the tour to be as short as possible.

Due to the nature of hiking, I figured this would sadly not be a symmetric problem (or can I convert my asymmetric graph to a symmetric one?), since going from high to low altitude is obviously easier than the other way around.

Since there are no restrictions regarding how many times I visit each point, as long as I visit all of them, it does not matter if the shortest path from a to d goes through b and c. Is this enough to say that triangle inequality holds and thus I have a metric problem?

I believe my problem is easier than TSP, so those algorithms do not fit this problem. I thought about using a minimum spanning tree, but I have a hard time applying it to this problem, which under the circumstances, should be a metric asymmetric directed graph?

What I really want are some pointers as to how I can come up with an approximation algorithm that will find a near optimal tour through all n points

Answer 1

I don't know how to solve your problem or show its NP-Hardness but you can find all pair shortest path to convert your graph to metric one, just replace $e_{a,b}$ with shortest path from a→b and if there isn't edge between $a,b$ add new edge with shortest path weight, now you can run some approximation for TSP to find approximation for your problem, as I know best approximation for TSP is currently $O({\log n \over \log{ \log n}})$. Base idea is using Held-Karp relaxation and finding special spanning tree then using method like Christofides algorithm. (it has some new definitions like Thin tree, ... which makes it harder than other methods for asymmetric case), you can also use known $O(\log n)$ approximations. Also I thought about your problem to approximate it with a minimum cycle cover, but I couldn't get good result. If I found anything I'll update this answer.