TSP heuristics for limited distance information this is my first question on Theoretical CS. :)

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 metric and
  I can make an estimate in advance with the euclidean distance, which provides a lower bound, but those estimates might be very bad.


Question:


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


Thanks in advance.
There is no algorithm that runs in time $o(n^2)$ on an $n$-point metric space and returns a tour with weight within a constant factor of the minimum weight: see the argument in Section 9 of this paper by Indyk.

On the other hand, if you just want an approximation to the weight of the optimal tour, without actually getting a tour, then you can use this algorithm by Czumaj and Sohler. Their algorithm runs in time which is nearly linear in $n/\varepsilon^{O(1)}$ and returns a $1+\varepsilon$ approximation to the weight of minimum weight spanning tree. Since the minimum weight spanning tree is a factor 2 approximation to the minimum weight TSP tour, this gives a factor $2+\varepsilon$ approximation for TSP.

Of course these are worst-case bounds, but I find it implausible to be able to find a good tour by querying $o(n^2)$ edges unless you know more about your metric space. Metric spaces are very general objects and it's easy to hide information while still satisfying the triangle inequality.