0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Also posted on CS.SE, and on MathOverflow 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:07
  • $\begingroup$ BTW there are a few things you should clarify. In my answer I assume that the input is a metric space on $n$ points, i.e. the complete graph with distances that satisfy the triangle inequality. (You can take a metric completion if the graph is not complete.) For the Euclidean estimate you mention: is there any guarantee how bad the estimate is? Is it at least always an overestimate? Or always an underestimate? Otherwise I don't know why you are even bringing it up. $\endgroup$ – Sasho Nikolov May 20 '15 at 2:13
  • $\begingroup$ I've edit my post. $\endgroup$ – aGer May 20 '15 at 7:19
  • $\begingroup$ BTW "my graphs are metrically" is not English and not totally clear. I guess you mean the algorithm has query access to the distances in an $n$ point metric space. Is that the case? Also when you say Euclidean distance, is the dimension constant? $\endgroup$ – Sasho Nikolov May 20 '15 at 7:32
  • $\begingroup$ I've edit my post again. Yes, this is the case. And again yes the dimension is constant. $\endgroup$ – aGer May 20 '15 at 7:55
3
$\begingroup$

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.

Improve this answer
$\endgroup$

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.