this is my first question on ComputerScience beta. :)
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.
So what are the TSP-Heuristika for those distance-matrices?
Thanks in advance.