<p>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 <a href="https://people.csail.mit.edu/indyk/metrics99.ps" rel="nofollow">paper by Indyk</a>.</p>

<p>On the other hand, if you just want an approximation to the <em>weight</em> of the optimal tour, without actually getting a tour, then you can use <a href="http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/Czumaj-Sohler-EstimMST.pdf" rel="nofollow">this algorithm</a> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-05-19T17:06:17.347Z
2015-05-19T17:06:17.347Z
Sasho Nikolov
<p>this is my first question on Theoretical CS. :)</p>

<p>I've posted a similiar <a href="https://mathoverflow.net/questions/207012/tsp-heuristics-for-limited-distance-information">question</a> on <a href="https://mathoverflow.net/">Mathoverflow</a> and a friendly user advised me to post my question on this site. </p>

<p><strong>Problem:</strong></p>

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

<p><strong>Question:</strong></p>

<blockquote>
  <p>So what are the TSP-Heuristika for those distance-matrices?</p>
</blockquote>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2015-05-19T19:07:37.077Z
[Also posted on CS.SE](http://cs.stackexchange.com/q/42756/755), and on MathOverflow and Math.SE.
Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). 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.
D.W.
CC BY-SA 3.0
2015-05-20T02:13:01.850Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-05-20T07:19:09.360Z
I've edit my post.
aGer
CC BY-SA 3.0
2015-05-20T07:32:28.627Z
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?
Sasho Nikolov
CC BY-SA 3.0
2015-05-20T07:55:21.280Z
I've edit my post again. Yes, this is the case. And again yes the dimension is constant.
aGer
CC BY-SA 3.0
2015-05-20T10:40:51.853Z
@SashoNikolov We have a constant dimension of 2.
aGer
<graph-theory><graph-algorithms><optimization><tsp><heuristics>
TSP heuristics for limited distance information
aGer
# TSP heuristics for limited distance information

(Asked by: username_0 on 2015-05-19)

this is my first question on Theoretical CS. :)

I've posted a similiar [question](https://mathoverflow.net/questions/207012/tsp-heuristics-for-limited-distance-information) on [Mathoverflow](https://mathoverflow.net/) 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.

**Tags:** graph-theory, graph-algorithms, optimization, tsp, heuristics

> **Comments:**
> **username_1**: [Also posted on CS.SE](http://cs.stackexchange.com/q/42756/755), and on MathOverflow and Math.SE. Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). 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.  
> **username_2**: 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.  
> **username_0**: I've edit my post.  
> **username_2**: 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?  
> **username_0**: I've edit my post again. Yes, this is the case. And again yes the dimension is constant.  
> **username_0**: @SashoNikolov We have a constant dimension of 2.  

---

## 1 answers

### Answer by username_2 on 2015-05-19. Score: 3 | Accepted answer

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](https://people.csail.mit.edu/indyk/metrics99.ps).

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](http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/Czumaj-Sohler-EstimMST.pdf) 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.


---

