# TSP heuristics for limited distance information [closed]

this is my first question on ComputerScience beta. :)

I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site.

Problem:

I'm looking for TSP heuristics in the case of limited information about the edges, for example: I have $n$ nodes but can only ask for $~\sim4n$ distances. My graphs are metrically and I can make an estimate in advance with the euclidean distance, but those estimates might be very bad.

Question:

So what are the TSP-Heuristika for those distance-matrices?

• "My graphs are metrically"? Does it mean that if you have $dist(a,b)$ and $dist(b,c)$ then $dist(a,c) \le dist(a,b) + dist(b,c)$ (triangle inequlaity)? – HEKTO May 19 '15 at 15:17