5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Is your graph planar? (Or are you hiking in a network of caves?) $\endgroup$ – JeffE Apr 28 '12 at 14:39
  • $\begingroup$ It is safe to assume that the graph is planar, yes $\endgroup$ – Casper Apr 29 '12 at 10:29
  • $\begingroup$ That makes the problem much easier; see courses.csail.mit.edu/6.889/fall11/lectures/L15.html $\endgroup$ – JeffE Apr 29 '12 at 16:07
  • $\begingroup$ @JeffE, As you said seems this problem is equivalence with TSP (with a little variation), but why? I prove it partially (I should cover more general possibilities), but my proof is not simple and obvious, but seems it's obvious for you, I think I missed something which eases this conversion, would you please tell me why this is obvious for you? $\endgroup$ – user742 Apr 29 '12 at 20:55
  • $\begingroup$ For each pair of vertices $(u,v)$, redefine the weight of edge $uv$ to be the shortest path distance from $u$ to $v$. Now three facts are easy to prove. (1) The optimal tours in the original graph and new graph have identical weight. (2) The optimal tour in the new graph never visits a vertex more than once. (3) Edge weights in the new graph obey the triangle inequality. So in the new graph, the problem is precisely metric traveling salesman. $\endgroup$ – JeffE Apr 30 '12 at 7:10
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I can't help but wonder if a minimum spanning tree would be any good. Since no shortest route can ever be shorter than the MST, and considering that I am allowed to go back to previously visited vertices, the MST would in theory be atleast a 2-approximation of my hiking problem? $\endgroup$ – Casper Apr 29 '12 at 10:31
  • 1
    $\begingroup$ @Casper, No MST is not good for you, except your problem is on undirected graphs, in that case there is 3/2 approximation, see christofides algorithm. In the paper I offered you they using flow to find a good tree (named it Thin tree), the main attribute of this tree is it's very thin :) means maximum min-cut over all possible spanning trees in the graph is minimized, I think this can get some intuition why for asymmetric case this tree is useful. However I have a strong feeling which says your problem belongs to $P$ :) $\endgroup$ – user742 Apr 29 '12 at 10:41
  • $\begingroup$ I will have to read the paper through thoroughly before I can grasp it fully, but for now I will mark your post as the answer, since it indeed does sound like something I can use. Thank you very much for taking the time to answer! $\endgroup$ – Casper Apr 29 '12 at 11:21
  • $\begingroup$ @Casper, I don't think my post is an answer, I think if you let it open for more time it can have better answers, and one thing my referenced paper is hard (it takes time to read, except you are expert in related feilds), you can use simpler algorithms and too many other heuristics. But also you can implement algorithm without concerning about its correctness proof. $\endgroup$ – user742 Apr 29 '12 at 11:23
  • $\begingroup$ I already considered finding all pair shortest path and your post confirmed me in that route, instead of presenting me with something completely different. My problem does not require me to have the absolute state-of-the-art solution, as long as it performs reasonably well. The formal proof of the approach is not really of any concern, since this is purely out of own interest in algorithmic techniques $\endgroup$ – Casper Apr 29 '12 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.