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.


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.


closed as off-topic by Gilles May 19 '15 at 22:07

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ "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)? $\endgroup$ – HEKTO May 19 '15 at 15:17
  • $\begingroup$ By 'metrically' i do not mean the euclidean distance. $\endgroup$ – aGer May 19 '15 at 15:22
  • $\begingroup$ You mentioned euclidean distance in your question... Anyway, you have to describe your class of graphs very precisely. May be you should insert some word after the "metrically" $\endgroup$ – HEKTO May 19 '15 at 17:42
  • 1
    $\begingroup$ Also posted on MathOverflow, and on CSTheory.SE and Math.SE. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$ – D.W. May 19 '15 at 19:09
  • $\begingroup$ I am closing this question (even though it is on-topic) because it has also been posted on Theoretical Computer Science and is answered there. $\endgroup$ – Gilles May 19 '15 at 22:07